hdu 3480 기울기 dp

사고방식: 매우 일반적인 경사율 dp

#include<cstdio>

#include<cstring>

#include<iostream>

#include<algorithm>

#define Maxn 10010

#define LL int

using namespace std;

LL dp[Maxn][2],num[Maxn];

int que[Maxn*10];

inline LL getleft(int x,int j,int k)

{

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

}

inline LL getright(int j,int k)

{

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

}

int main()

{

    int n,m,i,j,head,rear,t,Ca=0;

    int now,pre;

    scanf("%d",&t);

    while(t--){

        memset(dp,0,sizeof(dp));

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

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

            scanf("%d",num+i);

        sort(num+1,num+n+1);

        now=1,pre=0;

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

            dp[i][now]=(num[i]-num[1])*(num[i]-num[1]);

        for(j=1;j<m;j++){

            head=1,rear=0;

            que[++rear]=j-1;

            now=!now;

            pre=!pre;

            for(i=j;i<=n;i++){

                while(head<rear&&getleft(pre,que[head+1],que[head])<getright(que[head+1],que[head])*num[i])

                    head++;

                dp[i][now]=dp[que[head]][pre]+(num[i]-num[que[head]+1])*(num[i]-num[que[head]+1]);

                while(head<rear&&getleft(pre,i,que[rear])*getright(que[rear],que[rear-1])<=getleft(pre,que[rear],que[rear-1])*getright(i,que[rear]))

                    rear--;

                que[++rear]=i;

            }

        }

        printf("Case %d: %d
",++Ca,dp[n][now]);

    }

    return 0;

}