这个 基本上和上一个 一样。
#include <bits/stdc++.h> const long long mod = 1e9+7; const double ex = 1e-10; #define inf 0x3f3f3f3f #define iinf 0x3f3f3f3f3f3f3f3f using namespace std; long long dp[3011][5011]; long long sum[5011]; long long Tsum[5011]; int Q[3011][5011]; int head[3011]; int tail[3011]; double getk(int a,int b,int k) // get the slope { return (1.0*dp[k][a] - 1.0*Tsum[a] + 1.0*a*sum[a] - 1.0*(1.0*dp[k][b] - 1.0*Tsum[b] + 1.0*b*sum[b])) /(1.0*a-1.0*b); } int main() { int N,M; cin >> N >> M; memset(dp,iinf,sizeof(dp)); memset(sum,0,sizeof(sum)); memset(Tsum,0,sizeof(Tsum)); int a; for (int i = 1;i<=N; i++){ scanf("%d",&a); sum[i] += sum[i-1]+a; Tsum[i] += Tsum[i-1] + a*i; } for (int i = 0;i<=M; i++) head[i]=2,tail[i]=1,dp[i][0] = 0; for (int i = 1;i<=N;i++) for (int j = 1 ;j<=min(i,M);j++) { while (head[j-1]>tail[j-1]+1 && sum[i]>getk(Q[j-1][tail[j-1]+1],Q[j-1][tail[j-1]],j-1)) tail[j-1]++; // Find the best shift && Drop some shift because of the increase of sum int kk = Q[j-1][tail[j-1]]; dp[j][i] = dp[j-1][kk] - kk*(sum[i]-sum[kk]) + Tsum[i] - Tsum[kk];//Shift while (head[j]>tail[j]+1 && getk(i,Q[j][head[j]-1],j)<getk(Q[j][head[j]-1],Q[j][head[j]-2],j)) head[j]--;//Insert the shift i && Maintain the increase of the slope Q[j][head[j]++] = i;//Insert i } cout << dp[M][N] <<endl; return 0; }