hdu 1421引っ越し寝室【リニアDP】

2829 ワード

問題を捜すのを我慢して、2週間も考えてからやっとDPが出てきた.
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll inf=0x7fffffff;
ll dp[2048][2048],c[2048],ans;

int main()
{
    int i,j,n,k;
    while(~scanf("%d%d",&n,&k))
    {
        for(i=1; i<=n; i++)
            scanf("%lld",&c[i]);
        sort(c+1,c+n+1);
        for(i=0;i<=n;i++)
            for(j=0;j<=k;j++)
                {
                    if(j==0)
                        dp[i][j]=0;
                    else
                        dp[i][j]=inf;
                }
        dp[0][0]=0;
        //printf("%lld
",dp[]);
for(j=1;j<=k;j++) for(i=2*j;i<=n;i++) { dp[i][j]=min(dp[i-1][j],dp[i-2][j-1]+(c[i]-c[i-1])*(c[i]-c[i-1])); //printf("%d %d %lld %lld %lld
",i,j,dp[i][j],dp[i-1][j],dp[i-2][j-1]);
} ans=inf; for(i=1;i<=n;i++) ans=min(ans,dp[i][k]); printf("%lld
"
,ans); } return 0; }