bzoj4518: [Sdoi2016]征途--斜率DP

　　题目大意：把一个数列分成m段，计算每段的和sum，求所有的sum的方差，使其最小。

　　由方差*m可以化简得ans=m*sigma(ki^2)-sum[n]^2

　　很容易得出f[i][j]=min{f[i-1][k]+(sum[j]-sum[k])²}

　　很明显可以用斜率DP优化

　　令x<y<j

　　可以得出

　　然后就可以啦~~

　　另外值得注意的一点是。。dy和dx最好用下标大的减去下标小的，防止不等号颠倒

　　因为这个问题调了快两个小时T T

 1 #include<stdio.h>
 2 #include<string.h>
 3 #include<algorithm>
 4 #define LL long long
 5 #define maxn 3005
 6 using namespace std;
 7 int n,m,u,head,tail,q[maxn*4];
 8 LL sum[maxn],f[maxn][maxn];
 9 
10 LL pow(LL x){
11     return x*x;
12 }
13 
14 LL dy(int i, int x, int y){
15     return f[i][y]+pow(sum[y])-(f[i][x]+pow(sum[x]));
16 }
17 
18 LL dx(int x, int y){
19     return sum[y]-sum[x];
20 }
21 
22 int main(){
23     scanf("%d%d", &n, &m);
24     for (int i=1; i<=n; i++){
25         scanf("%d", &u);
26         sum[i]=sum[i-1]+u;
27         f[1][i]=pow(sum[i]);
28     }
29     f[0][0]=0;
30     for (int i=2; i<=m; i++){
31         head=0; tail=0;
32         q[tail++]=i-1;
33         for (int j=i; j<=n; j++){
34             while (head+1<tail){
35                 int x=q[head], y=q[head+1];
36                 if (dy(i-1,x,y)<=2*(LL)sum[j]*dx(x,y)) head++;
37                 else break;
38             }
39             int k=q[head];
40             f[i][j]=f[i-1][k]+pow(sum[j]-sum[k]);
41             while (head+1<tail){
42                 int x=q[tail-2], y=q[tail-1];
43                 if (dy(i-1,x,y)*dx(y,j)>=dy(i-1,y,j)*dx(x,y)) tail--;
44                 else break;
45             }
46             q[tail++]=j;
47         }
48     }
49     printf("%lld
", m*f[m][n]-pow(sum[n]));
50     return 0;
51 }