scanf("%d",&arr[i]),sum[i] = arr[i] + sum[i-1];
Initial();
int ans = Solve_DP();
printf("%d\n",ans);
}
}
[cpp]
//cost[k+1][i]=cost[1][i]-cost[1][k]-sum[k]*(sum[i]-sum[k])
//dp[i][j]=dp[k][j-1]+cost[1][i]-cost[1][k]-sum[k]*(sum[i]-sum[k])
// =dp[k][j-1]-cost[1][k]+sum[k]^2-sum[i]*sum[k]+cost[1][i]
//斜率优化一
#include
#include
#define MAX 1100
#define INF (1<<30)
struct point {
int x,y;
}pot[MAX];
int head,tail,qu[MAX];
int n,m,arr[MAX],cost[MAX];
int sum[MAX],sum2[MAX],dp[MAX][MAX];
void Initial() {
for (int i = 1; i <= n; ++i) {
sum[i] = arr[i] + sum[i-1];
cost[i] = cost[i-1] + arr[i] * sum[i-1];
dp[i][0] = cost[i];
}
}
int CheckIt(point p0,point p1,point p2) {
return (p0.x-p1.x) * (p0.y-p2.y) - (p0.y-p1.y) * (p0.x-p2.x) <= 0;
}
int NotBest(point p0,point p1,int k) {
return p0.y - k * p0.x > p1.y - k * p1.x;
}
int Solve_DP() {
int i,j,k;
for (j = 1; j <= m; ++j) {
head = 0,tail = 0;
qu[tail] = 0;
for (i = j + 1; i <= n; ++i) {
pot[i].x = sum[i-1];
pot[i].y = dp[i-1][j-1] - cost[i-1] + sum[i-1] * sum[i-1];
while (head <= tail - 1 &&
CheckIt(pot[qu[tail-1]],pot[qu[tail]],pot[i])) tail--;
qu[++tail] = i;
while (head + 1 <= tail &&
NotBest(pot[qu[head]],pot[qu[head+1]],sum[i])) head++;
k = qu[head];
//dp[i][j] = y - k * x + c
dp[i][j] = pot[k].y - sum[i] * pot[k].x + cost[i];
}
}
return dp[n][m];
}
int main()
{
int i,j,k;
while (scanf("%d%d",&n,&m),n+m) {
for (i = 1; i <= n; ++i) www.2cto.com
scanf("%d",&arr[i]),sum[i] = arr[i] + sum[i-1];
Initial();
int ans = Solve_DP();
printf("%d\n",ans);
}
}