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;
}