HDU1421

提交啦n次一直WA，这个bug找啦几个小时，最终才发现数组开小啦，真是遗憾。这是一个典型的DP问题，题目要求从n个中选出k对使得最终疲劳度最小。首先对物品质量a[n]进行一次排序，用dp[i][j]表示从前i个物品中选取j对物品的最小疲劳度，现在我们来探讨状态转移方程,对于第i个物品，我们有选和不选两种选择(当i=2*j时必须选)，若选择第i个物品则为啦使得最终疲劳度最小，第i个物品一定与第i-1个物品配对（为什么会是这样?）,那么还需要在前i-2个物品中选取j-1对，那么此时dp[i][j]=dp[i-2][j-1]+(a[i]-a[i-1])*(a[i]-a[i-1])，若不选第i个物品，则问题转化为从前i-1个物品中选取j对物品，那么dp[i][j]=dp[i-1][j];于是得到以下状态转移方程：

dp[i][j]=min{dp[i-1][j,dp[i-2][j-1]+(a[i]-a[i-1])*(a[i]-a[i-1])}(特别的当i=2*j时候，只能dp[i][j]=dp[i-2][j-1]+(a[i]-a[i-1])*(a[i]-a[i-1]));

先来证明为什么在前面方程中若选第i个物品则它必须与第i-1个物品配对。假设a[i]与a[k](1<=k<=i-2)配对可以使得d[i][j]达到最小,若a[k]之前没有配对过，（1）若a[i-1]之前也没有参与配对，则用(a[i]-a[i-1])*a[i]-a[i-1])代替(a[i]-a[k])*(a[i]-a[k])可以使得d[i][j]达到更小，与假设矛盾.(2)若a[i-1]之前有与某a[m]配对(0<m<i-1)，则完全可以用（a[i-1],a[i]）,(a[k],a[m])配对来代替(a[i],a[k]),(a[i-1],a[m])来达到最小与假设矛盾.若a[k]之前有与某a[k1]配对过，然后问题转换为再来寻找与a[k1]配对的数a[k2]...直到遇到没有配对的数停止，总能得到a[i]与a[i-1]是最佳匹配。

#include<iostream>
#include<algorithm>
using namespace std;
#define max 2000
int dp[max][1000];
int DP(int a[],int n, int k);
int main(){
int n,k,i;
int a[max];
while (cin >> n >> k){
for (i = 1; i <= n; i++)
cin >> a[i];
sort(a + 1, a + n + 1);
cout << DP(a, n, k) << endl;
}
return 0;
}
int DP(int a[], int n, int k){
int i, j,t;
for (i = 0; i <= n; i++)
dp[i][0] =0; //将第一列初始化为0
for (i = 2; i <= n;i++)
for (j = 1; j <= k&&j <= i / 2; j++){ /*当j>i/2无意义，可以不计算*/
t = dp[i - 2][j - 1] + (a[i] - a[i - 1])*(a[i] - a[i - 1]);
if (j * 2 == i)
dp[i][j] = t; //出现i==2j时特殊处理，因为此时不存在dp[i-1][j]
else
dp[i][j] = t < dp[i - 1][j] ? t : dp[i - 1][j];
}
return dp[n][k];
}

巴特西

HDU1421

最新文章

热门文章