$dp$，斜率优化。
有一种很直观的$dp$方式：
设$dp[j][i]$表示前$i$个数字，分成了$j$组的最小代价。$dp$转移方程很容易写，斜率优化也很容易。斜率优化之后时间复杂度为$O(n^2)$，最坏情况大约是是$5000$万的复杂度。我尝试了一下，但是不幸超时了。但是当我特判掉$s=0$的情况（该情况肯定是分成$n$组）之后，去尝试分$1000$组，$500$组，$250$组......能否$AC$，最终发现后台数据除去$s=0$的情况之后，最坏的情况是分成$166$组就可以得到最优解。因此这样$500ms$水过去了。
#pragma comment(linker, "/STACK:1024000000,1024000000") #include<cstdio> #include<cstring> #include<cmath> #include<algorithm> #include<vector> #include<map> #include<set> #include<queue> #include<stack> #include<ctime> #include<iostream> using namespace std; typedef long long LL; const double pi=acos(-1.0),eps=1e-10; void File() { freopen("D:\in.txt","r",stdin); freopen("D:\out.txt","w",stdout); } template <class T> inline void read(T &x) { char c = getchar(); x = 0; while(!isdigit(c)) c = getchar(); while(isdigit(c)) { x = x * 10 + c - '0'; c = getchar(); } } int dp[2][10010]; int n,s; int q[10010],f1,f2; int sumT[10010],sumF[10010]; int flag; int ans; bool delete1(int t,int a,int b,int c) { if( dp[flag^1][b]-(t+1)*s*sumF[b]-sumT[c]*sumF[b]<= dp[flag^1][a]-(t+1)*s*sumF[a]-sumT[c]*sumF[a] ) return 1; return 0; } bool delete2(int t,int a,int b,int c) { if( ((dp[flag^1][c]-(t+1)*s*sumF[c])-(dp[flag^1][b]-(t+1)*s*sumF[b]))*(sumF[b]-sumF[a])<= ((dp[flag^1][b]-(t+1)*s*sumF[b])-(dp[flag^1][a]-(t+1)*s*sumF[a]))*(sumF[c]-sumF[b]) ) return 1; return 0; } int main() { scanf("%d%d",&n,&s); for(int i=1; i<=n; i++) { int tt,ff; scanf("%d%d",&tt,&ff); sumT[i]=sumT[i-1]+tt; sumF[i]=sumF[i-1]+ff; } if(s==0) { ans=0; for(int i=1; i<=n; i++) ans=ans+sumT[i]*(sumF[i]-sumF[i-1]); printf("%d ",ans); return 0; } flag=0; ans=0x7FFFFFFF; for(int i=1; i<=n; i++) dp[flag][i]=(sumT[i]+s)*sumF[i]; ans=min(ans,dp[flag][n]); for(int j=2; j<=min(166,n); j++) { flag=flag^1; f1=f2=0; q[0]=j-1; for(int i=j; i<=n; i++) { while(1) { if(f2-f1+1<2) break; if(delete1(j-1,q[f1],q[f1+1],i)) f1++; else break; } dp[flag][i]=dp[flag^1][q[f1]]+(j*s+sumT[i])*(sumF[i]-sumF[q[f1]]); while(1) { if(f2-f1+1<2) break; if(delete2(j-1,q[f2-1],q[f2],i)) f2--; else break; } f2++; q[f2]=i; } ans=min(ans,dp[flag][n]); } printf("%d ",ans); return 0; }
水过去的方法当然是不可取的，复杂度太高了。看了神犇博客，发现这题可以$O(n)$做。
设$dp[i]$表示以$i$为任务起点，到达终点的最小代价。
那么，$dp[i]=min(dp[x]+(sumF[n]-sumF[i-1])*(s+sumT[x-1]-sumT[i-1]))$。
进行斜率优化之后时间复杂度降到了$O(n)$。
#pragma comment(linker, "/STACK:1024000000,1024000000") #include<cstdio> #include<cstring> #include<cmath> #include<algorithm> #include<vector> #include<map> #include<set> #include<queue> #include<stack> #include<ctime> #include<iostream> using namespace std; typedef long long LL; const double pi=acos(-1.0),eps=1e-10; void File() { freopen("D:\in.txt","r",stdin); freopen("D:\out.txt","w",stdout); } template <class T> inline void read(T &x) { char c = getchar(); x = 0; while(!isdigit(c)) c = getchar(); while(isdigit(c)) { x = x * 10 + c - '0'; c = getchar(); } } int n,s; int T[10010],F[10010],dp[10010]; int sumT[10010],sumF[10010]; int f1,f2,q[10010]; bool delete1(int a,int b,int c) { int A=sumF[n]-sumF[c-1]; if(dp[a]+A*sumT[a-1]>=dp[b]+A*sumT[b-1]) return 1; return 0; } bool delete2(int a,int b,int c) { if((dp[b]-dp[a])*(sumT[c-1]-sumT[b-1])<= (dp[c]-dp[b])*(sumT[b-1]-sumT[a-1])) return 1; return 0; } int main() { scanf("%d%d",&n,&s); for(int i=1; i<=n; i++) { scanf("%d%d",&T[i],&F[i]); sumT[i]=sumT[i-1]+T[i]; sumF[i]=sumF[i-1]+F[i]; } f1=f2=0; q[0]=n+1; for(int i=n;i>=1;i--) { while(1) { if(f2-f1+1<2) break; if(delete1(q[f1],q[f1+1],i)) f1++; else break; } dp[i]=dp[q[f1]]+(sumF[n]-sumF[i-1])*(s+sumT[q[f1]-1]-sumT[i-1]); while(1) { if(f2-f1+1<2) break; if(delete2(q[f2-1],q[f2],i)) f2--; else break; } f2++; q[f2]=i; } printf("%d ",dp[1]); return 0; }