HDU 3480 Division

$dp$，斜率优化。

和HDU 2829基本上是一样的。这题还比那题简单，得到斜率的式子很方便。

#pragma comment(linker, "/STACK:1024000000,1024000000")
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<vector>
#include<map>
#include<set>
#include<queue>
#include<stack>
#include<ctime>
#include<iostream>
using namespace std;
typedef long long LL;
const double pi=acos(-1.0),eps=1e-10;
void File()
{
    freopen("D:\in.txt","r",stdin);
    freopen("D:\out.txt","w",stdout);
}
template <class T>
inline void read(T &x)
{
    char c = getchar();
    x = 0;
    while(!isdigit(c)) c = getchar();
    while(isdigit(c))
    {
        x = x * 10 + c - '0';
        c = getchar();
    }
}

int T,n,m;
long long dp[10010][5010];
long long x[10010];
int q[10010],f1,f2;

bool delete1(int t,int a,int b,int c)
{
    if(dp[b][t]+x[b+1]*x[b+1]-dp[a][t]-x[a+1]*x[a+1]<2*x[c]*(x[b+1]-x[a+1])) return 1;
    return 0;
}

bool delete2(int t,int a,int b,int c)
{
    if((dp[c][t]+x[c+1]*x[c+1]-dp[b][t]-x[b+1]*x[b+1])*(x[b+1]-x[a+1])<=
       (dp[b][t]+x[b+1]*x[b+1]-dp[a][t]-x[a+1]*x[a+1])*(x[c+1]-x[b+1])
       ) return 1;
    return 0;
}

int main()
{
    scanf("%d",&T); int cas=1;
    while(T--)
    {
        scanf("%d%d",&n,&m);
        for(int i=1;i<=n;i++) scanf("%lld",&x[i]);
        sort(x+1,x+1+n);

        for(int i=1;i<=n;i++) dp[i][1]=(x[i]-x[1])*(x[i]-x[1]);
        for(int j=2;j<=m;j++)
        {
            f1=f2=0; q[f2]=j-1;
            for(int i=j;i<=n;i++)
            {
                while(1)
                {
                    if(f2-f1+1<2) break;
                    if(delete1(j-1,q[f1],q[f1+1],i)) f1++;
                    else break;
                }

                dp[i][j]=dp[q[f1]][j-1]+(x[i]-x[q[f1]+1])*(x[i]-x[q[f1]+1]);

                while(1)
                {
                    if(f2-f1+1<2) break;
                    if(delete2(j-1,q[f2-1],q[f2],i)) f2--;
                    else break;
                }

                f2++; q[f2]=i;
            }
        }

        printf("Case %d: %lld
",cas++,dp[n][m]);
    }
    return 0;
}