(A[j]+...+A[i])^2 = A[j]^2 + A[j+1]^2 + ... + A[i]^2 + 2* cost[j][i]; (沒(méi)有TeX寫這個(gè)就是不爽啊)
于是乎 cost[j+1][i] = ((sum[i]-sum[j])^2 - suma[i] + suma[j])/2 = -sum[i] * sum[j] + (suma[j] - sum[j]^2)/2 + (sum[i]^2 - suma[i])/2;
移項(xiàng)得 Y(j) = X(j)*sum[j] + dp[i][k] - C(i) 轉(zhuǎn)成了線性規(guī)劃問(wèn)題。 不難想到最優(yōu)解一定在凸包上。
#include<iostream>
#include<cstdio>
#include<cassert>
using namespace std;
#define re(i,n) for(int i = 0; i< n; i++)
const int N = 1001;
typedef long long ll;
ll dp[N][N];
ll num[N],pos[N][2],sum[N],suma[N];
int Q[N];
bool cal(int p0, int p1 , ll k){
return pos[p1][1] - pos[p0][1] < k * ( pos[p1][0] - pos[p0][0]);
}
ll cross( int p0, int p1, int p2){
return (pos[p0][0] - pos[p1][0] ) * ( pos[p0][1] - pos[p2][1] ) - ( pos[p0][1] - pos[p1][1]) * ( pos[p0][0] - pos[p2][0] );
}
int main(){
int n,m ;
while(~scanf("%d%d",&n,&m) && n){
re(i,n)
scanf("%lld",&num[i]);
re(i,n) sum[i] = (i == 0 ? 0 : sum[i-1]) + num[i];
re(i,n) dp[i][0] = ( i == 0 ? 0 : dp[i-1][0] + num[i] * sum[i-1]);
re(i,n) suma[i] = (i == 0 ? 0 : suma[i-1])+ num[i] * num[i];
for(int j = 1; j<=m ; j++) {
int head = 0 ,tail =0 ;
for(int i = j; i < n ; i++){
pos[i][0] = sum[i-1]; pos[i][1] = dp[i-1][j-1] + (suma[i-1] + sum[i-1]*sum[i-1])/2;
while(tail - head > 1 && cross(Q[tail-2] , Q[tail-1], i) <= 0) tail --;
Q[tail ++ ] = i;
while(tail - head > 1 && cal(Q[head], Q[head +1 ] , sum[i]) ) head ++;
dp[i][j] = pos[Q[head]][1] - pos[Q[head]][0] * sum[i] + (sum[i]*sum[i] - suma[i])/2;
}
}
cout<< dp[n-1][m] <<endl;
}
}
1 #include<iostream>
2 #include<cstdio>
3 #include<cassert>
4 using namespace std;
5 #define re(i,n) for(int i = 0; i< n; i++)
6 const int N = 1001;
7 typedef long long ll;
8 ll dp[N][N];
9 ll num[N],pos[N][2],sum[N],suma[N];
10 int Q[N];
11 bool cal(int p0, int p1 , ll k){
12 return pos[p1][1] - pos[p0][1] < k * ( pos[p1][0] - pos[p0][0]);
13 }
14 ll cross( int p0, int p1, int p2){
15 return (pos[p0][0] - pos[p1][0] ) * ( pos[p0][1] - pos[p2][1] ) - ( pos[p0][1] - pos[p1][1]) * ( pos[p0][0] - pos[p2][0] );
16 }
17 int main(){
18 int n,m ;
19 while(~scanf("%d%d",&n,&m) && n){
20 re(i,n)
21 scanf("%lld",&num[i]);
22 re(i,n) sum[i] = (i == 0 ? 0 : sum[i-1]) + num[i];
23 re(i,n) dp[i][0] = ( i == 0 ? 0 : dp[i-1][0] + num[i] * sum[i-1]);
24 re(i,n) suma[i] = (i == 0 ? 0 : suma[i-1])+ num[i] * num[i];
25 for(int j = 1; j<=m ; j++) {
26 int head = 0 ,tail =0 ;
27 for(int i = j; i < n ; i++){
28 pos[i][0] = sum[i-1]; pos[i][1] = dp[i-1][j-1] + (suma[i-1] + sum[i-1]*sum[i-1])/2;
29 while(tail - head > 1 && cross(Q[tail-2] , Q[tail-1], i) <= 0) tail --;
30 Q[tail ++ ] = i;
31 while(tail - head > 1 && cal(Q[head], Q[head +1 ] , sum[i]) ) head ++;
32 dp[i][j] = pos[Q[head]][1] - pos[Q[head]][0] * sum[i] + (sum[i]*sum[i] - suma[i])/2;
33 }
34 }
35 cout<< dp[n-1][m] <<endl;
36 }
37 }
38