AcWing 300. 任务安排1（ 前缀和 dp优化）

#include<iostream>
#include<limits.h>
#include<cstring>
#define int long long
using namespace std;
const int N=5010;
int n,f[N],sumt[N],sumc[N],s;
//f[i][j]=f[k][j-1]+(t[1]+...+t[i]+j*s)*(c[k+1]+...+c[i])
signed main(){
    cin>>n>>s;
    for(int i=1;i<=n;i++){
        int t,c;
        cin>>t>>c;
        sumt[i]=sumt[i-1]+t;
        sumc[i]=sumc[i-1]+c;
    }
    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[j]+sumt[i]*(sumc[i]-sumc[j])+s*(sumc[n]-sumc[j]),f[i]);
        }
    }
    cout<<f[n]<<endl;
}