C++14(g++5.4) 解法, 执行用时: 10ms, 内存消耗: 8352K, 提交时间: 2020-08-03 20:58:30

#include<bits/stdc++.h>
#pragma GCC optimize("Ofast,no-stack-protector")
#include<iostream>
#include<cstring>
#include<string>
#include<cstdio>
#include<list>
#include<vector>
#include<cmath>
#include<queue>
//#include <tr1/unordered_map>
#include<algorithm>
#define int long long
#define ull signed long long
#define mm 1000007
//#define N 500008
//#define M 2000007
#define oo 100000000000
#define ll long long
//ios::sync_with_stdio(false);
#define mod 998244353

using namespace std;
//////////////////////////////////////////////////////////
int tt;
int n;
int sumt[mm];
int sumc[mm];
int t;int c;
int s;
int f[mm];
int q[mm];

signed main()
{
   // scanf("%lld",&tt);
   tt=1;
    while(tt--)
    {
        scanf("%lld",&n);
        scanf("%lld",&s);
        for(int i=1;i<=n;i++)
        {
            scanf("%lld%lld",&t,&c);
            sumt[i]=sumt[i-1]+t;
            sumc[i]=sumc[i-1]+c;
        }
        memset(f,0x3f,sizeof(f));
        f[0]=0;
        int l=1;
        int r=1;
        q[l]=0;
        for(int i=1;i<=n;i++)
        {
            while(l<r&&(f[q[l+1]]-f[q[l]])<=(s+sumt[i])*(sumc[q[l+1]]-sumc[q[l]])){l++;}
            f[i]=f[q[l]]-(s+sumt[i])*sumc[q[l]]+sumt[i]*sumc[i]+s*sumc[n];
            while(l<r&&(f[q[r]]-f[q[r-1]])*(sumc[i]-sumc[q[r]])>=(f[i]-f[q[r]])*(sumc[q[r]]-sumc[q[r-1]])){r--;}
            q[++r]=i;
        }
        cout<<f[n]<<endl;
    }
    return 0;
}

Java 解法, 执行用时: 90ms, 内存消耗: 17836K, 提交时间: 2021-09-10 19:08:52

import java.io.*;

public class Main {
    static final int LEN = 10010;
    public static void main(String[] args) throws IOException {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(in.readLine());
        int S = Integer.parseInt(in.readLine());
        long[] T = new long[N + 1];
        long[] C = new long[N + 1];
        for (int i = 1; i <= N; i++) {
            String[] lines = in.readLine().split(" ");
            T[i] = T[i - 1] + Integer.parseInt(lines[0]);
            C[i] = C[i - 1] + Integer.parseInt(lines[1]);
        }
        in.close();
        int[] queue = new int[LEN];
        long[] dp = new long[N + 1];
        int head = 0, tail = 0;
        for (int i = 1; i <= N; i++) {
            while (head < tail && (dp[queue[head + 1]] - dp[queue[head]]) <= (T[i] + S) * (C[queue[head + 1]] - C[queue[head]])) head++;
            int j = queue[head];
            dp[i] = dp[j] - (T[i] + S) * C[j] + T[i] * C[i] + S * C[N];
            while (head < tail && (dp[queue[tail]] - dp[queue[tail - 1]]) * (C[i] - C[queue[tail - 1]]) >=
            (dp[i] - dp[queue[tail - 1]]) * (C[queue[tail]] - C[queue[tail - 1]])) tail--;
            queue[++tail] = i;
        }
        System.out.println(dp[N]);
    }
}

C++(clang++ 11.0.1) 解法, 执行用时: 66ms, 内存消耗: 616K, 提交时间: 2022-12-28 13:15:26

#include<bits/stdc++.h>
using namespace std;
int f[10005],sa[10005],sc[10005],a[10005],c[10005];
int main(){
    int n,s; cin>>n>>s;
    for(int i=1;i<=n;i++) cin>>a[i]>>c[i];
    for(int i=1;i<=n;i++) sa[i]=sa[i-1]+a[i],sc[i]=sc[i-1]+c[i];
    memset(f,0x3f,sizeof f);
    f[0]=0;
    for(int i=1;i<=n;i++){
        for(int j=0;j<i;j++){
            f[i]=min(f[i],f[j]+sa[i]*(sc[i]-sc[j])+s*(sc[n]-sc[j]));
        }
    }
    cout<<f[n];
}