hdu 3480 Division(斜率优化DP)

题目链接：hdu 3480 Division

题意：

给你一个有n个数的集合S，现在让你选出m个子集合，使这m个子集合并起来为S，并且每个集合的(max-min)² 之和要最小。

题解：

运用贪心的思想，肯定首先将全部的数排好序，然后设dp[i][j]表示前j个数分为i个集合的最优解。

则有dp[i][j]=min{dp[i-1][k]+(a[j]-a[k+1])²}(0<k<j)。

这样写出来是三层for的dp，考虑用斜率优化降维。

假设l<k<j,对于dp[i][j]，k到j为一个集合比l到j为一个集合更优。

则有：dp[i-1][k]+(a[j]-a[k+1])²<=dp[i-1][l]+(a[j]-a[l+1])²。

整理得 dp[i-1][k]+a[k+1]² -dp[i-1][l]+a[l+1]² /a[k+1]-a[l-1]<=2*a[j]。

然后就是y1-y2/x1-x2<=L的斜率形式了。

#include<bits/stdc++.h>
#define F(i,a,b) for(int i=a;i<=b;++i)
using namespace std;

const int N=10007;

int t,n,m,dp[2][N],Q[N],a[N],ic;

int getx(int k,int l){return a[k+1]-a[l+1];}
int gety(int i,int k,int l){return dp[i][k]+a[k+1]*a[k+1]-dp[i][l]-a[l+1]*a[l+1];}
int check(int i,int j,int k,int l){return gety(i,j,k)*getx(k,l)<=gety(i,k,l)*getx(j,k);}

int main()
{
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d%d",&n,&m);
        F(i,1,n)scanf("%d",a+i);
        sort(a+1,a+1+n);
        F(i,1,n)dp[0][i]=(a[i]-a[1])*(a[i]-a[1]);
        F(i,2,m)
        {
            int now=0,head=1,tail=0;
            Q[++tail]=i-1;
            F(j,i,n)
            {
                while(head<tail&&check(i&1,j,Q[tail],Q[tail-1]))tail--;//维护一个“下凸”曲线
                Q[++tail]=j;
                while(head<tail&&gety(i&1,Q[head+1],Q[head])<=getx(Q[head+1],Q[head])*2*a[j])head++;
                dp[(i&1)^1][j]=dp[i&1][Q[head]]+(a[j]-a[Q[head]+1])*(a[j]-a[Q[head]+1]);
            }
        }
        printf("Case %d: %d\n",++ic,dp[(m&1)^1][n]);
    }
    return 0;
}