HDU 3480 division

提示：扫一扫查出行
【扫一扫了解最新限行尾号】
复制提示

题目大意：一个有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] 。

于是，可知有效的决策点构成了下凸包。

通过单调队列可以解决该问题。

 #include<cstdio>

 #include<iostream>

 #include<cstdlib>

 #include<cstring>

 #include<algorithm>

 #define MAXN 10005

 using namespace std;

 int f[][MAXN],row;

 int que[MAXN],head,tail,t,n,m;

 int num[MAXN];

 int up(int j,int k)

 {

     return f[!row][j]+num[j+]*num[j+]-f[!row][k]-num[k+]*num[k+];

 }

 int down(int j,int k)

 {

     return (num[j+]-num[k+])*;

 }

 bool turnup(int i,int j,int k) //向上为1，向下为0

 {

       int y2=up(i,j),x2=down(i,j),y1=up(j,k),x1=down(j,k);

     if(x1*y2>x2*y1)return ;

     else return ;

 }

 int main()

 {

     scanf("%d",&t);

     for(int cas=;cas<=t;cas++)

     {

         scanf("%d%d",&n,&m);

         for(int i=;i<=n;i++)

             scanf("%d",&num[i]);

         sort(num+,num+n+);

         head=tail=;

         que[tail++]=;

         for(int i=;i<=n;i++)

             f[][i]=(num[i]-num[])*(num[i]-num[]);

         for(int r=;r<=m;r++)

         {

         row=(r&);

         head=tail=;

         que[tail++]=r-;

         for(int i=r;i<=n;i++)

         {

             while(head<tail-&&up(que[head+],que[head])<=down(que[head+],que[head])*num[i])

                 head++;

             f[row][i]=f[!row][que[head]]+(num[i]-num[que[head]+])*(num[i]-num[que[head]+]);

             while(head<tail-&&(turnup(i,que[tail-],que[tail-])==))

                 tail--;

             que[tail++]=i;

         }

     }

     printf("Case %d: %d\n",cas,f[m&][n]);

     memset(f,,sizeof f);

     memset(que,,sizeof que);

     }

 }