题目大意：一个有n个数的集合，现在要求将他分成m+1个子集，对子集i设si表示该集合中最大数与最小数的差的平方。求所有si的和的最小值。n<=10000,m<=5000.
分析：最优解的ｍ个集合肯定不会相交，也不会出现空集，而且每个子集的数必定是连续的。
所以可以将ｎ个数先排序，在来进行dp求解。
f[i][j]表示前j个数分成i个集合的最优解。
转移方程为：f[i][j]=min(f[i-1][k]+(num[j]-num[k+1])^2
设决策点k1<k2,若有k2比k1更优，则有：
f[i-1][k1]+num[k1+1]^2-2*num[j]*num[k1+1]<f[i-1][k2]+num[k2+1]^2-2*num[j]*num[k2+1]
将关于j的项移到右边，关于k1、k2的项移到左边：
f[i-1][k1]+num[k1+1]^2-(f[i-1][k2]+num[k2+1]^2)>2num[j]*(num[k1+1]-num[k2+1])
令yk1=f[i-1][k1]+num[k1+1]^2,xk1=num[k1+1],
则上式可以转化为：(yk2-yk1)/(2(xk2-xk1))<num[j] 。
于是，可知有效的决策点构成了下凸包。
通过单调队列可以解决该问题。
1 #include<cstdio> 2 #include<iostream> 3 #include<cstdlib> 4 #include<cstring> 5 #include<algorithm> 6 #define MAXN 10005 7 using namespace std; 8 int f[2][MAXN],row; 9 int que[MAXN],head,tail,t,n,m; 10 int num[MAXN]; 11 int up(int j,int k) 12 { 13 return f[!row][j]+num[j+1]*num[j+1]-f[!row][k]-num[k+1]*num[k+1]; 14 } 15 int down(int j,int k) 16 { 17 return (num[j+1]-num[k+1])*2; 18 } 19 bool turnup(int i,int j,int k) //向上为1，向下为0 20 { 21 int y2=up(i,j),x2=down(i,j),y1=up(j,k),x1=down(j,k); 22 if(x1*y2>x2*y1)return 1; 23 else return 0; 24 } 25 int main() 26 { 27 scanf("%d",&t); 28 for(int cas=1;cas<=t;cas++) 29 { 30 scanf("%d%d",&n,&m); 31 for(int i=1;i<=n;i++) 32 scanf("%d",&num[i]); 33 sort(num+1,num+n+1); 34 head=tail=1; 35 que[tail++]=0; 36 for(int i=1;i<=n;i++) 37 f[1][i]=(num[i]-num[1])*(num[i]-num[1]); 38 for(int r=2;r<=m;r++) 39 { 40 row=(r&1); 41 head=tail=1; 42 que[tail++]=r-1; 43 for(int i=r;i<=n;i++) 44 { 45 while(head<tail-1&&up(que[head+1],que[head])<=down(que[head+1],que[head])*num[i]) 46 head++; 47 f[row][i]=f[!row][que[head]]+(num[i]-num[que[head]+1])*(num[i]-num[que[head]+1]); 48 while(head<tail-1&&(turnup(i,que[tail-1],que[tail-2])==0)) 49 tail--; 50 que[tail++]=i; 51 } 52 } 53 printf("Case %d: %d ",cas,f[m&1][n]); 54 memset(f,0,sizeof f); 55 memset(que,0,sizeof que); 56 57 } 58 }