題目：搬寢室

?

典型的DP，狀態方程：

dp[k][i]=min(dp[k-1][i-2]+(a[i]-a[i-1])^2,dp[k][i-1]);???????? dp[k][i] 表示 k 對物品在前 i 個物品的最小值

#include<iostream>
#include<stdio.h>
#include<algorithm>
#define N 2005
using namespace std;
int dp[N/2][N];
int a[N];void Init(int k)
{int i;dp[k][2*k]=0;for(i=2;i<=2*k;i+=2)dp[k][2*k]+=(a[i]-a[i-1])*(a[i]-a[i-1]);
}int work(int n,int m)
{int i,k;sort(a+1,a+n+1);for(k=1;k<=m;k++)  Init(k);for(k=1;k<=m;k++){for(i=2*k+1;i<=n;i++){dp[k][i]=min(dp[k][i-1],dp[k-1][i-2]+(a[i]-a[i-1])*(a[i]-a[i-1]));}}return dp[m][n];
}int main()
{int n,k;while(scanf("%d%d",&n,&k)!=EOF){int i;for(i=1;i<=n;i++)cin>>a[i];int ans=work(n,k);printf("%d\n",ans);}return 0;
}

?

?

總結

以上是生活随笔為你收集整理的HDU1421 搬寝室的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。