题目大意:把一个数列分成m段,计算每段的和sum,求所有的sum的方差,使其最小。
由方差*m可以化简得ans=m*sigma(ki^2)-sum[n]^2
很容易得出f[i][j]=min{f[i-1][k]+(sum[j]-sum[k])2}
很明显可以用斜率DP优化
令x<y<j
可以得出
然后就可以啦~~
另外值得注意的一点是。。dy和dx最好用下标大的减去下标小的,防止不等号颠倒
因为这个问题调了快两个小时T T
#include<stdio.h> #include<string.h> #include<algorithm> #define LL long long #define maxn 3005 using namespace std; ]; LL sum[maxn],f[maxn][maxn]; LL pow(LL x){ return x*x; } LL dy(int i, int x, int y){ return f[i][y]+pow(sum[y])-(f[i][x]+pow(sum[x])); } LL dx(int x, int y){ return sum[y]-sum[x]; } int main(){ scanf("%d%d", &n, &m); ; i<=n; i++){ scanf("%d", &u); sum[i]=sum[i-]+u; f[][i]=pow(sum[i]); } f[][]=; ; i<=m; i++){ head=; tail=; q[tail++]=i-; for (int j=i; j<=n; j++){ <tail){ ]; ,x,y)<=*(LL)sum[j]*dx(x,y)) head++; else break; } int k=q[head]; f[i][j]=f[i-][k]+pow(sum[j]-sum[k]); <tail){ ], y=q[tail-]; ,x,y)*dx(y,j)>=dy(i-,y,j)*dx(x,y)) tail--; else break; } q[tail++]=j; } } printf("%lld\n", m*f[m][n]-pow(sum[n])); ; }