题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1421
状态转移方程有点困难。。。orz,得练那。。。
View Code
1 /* 2 题目大意： 3 给定n个物品，每个物品有重量， 4 从中选出m对，使得这m对物品重量差的平方和最小。 5 疲劳度：m对物品重量差的平方和 6 分析与解题思路 7 先对n中物品的重量排序 8 令dp[i][j]表示前i个物品中选j对的最小疲劳度。 9 则dp[i][j]可能含有第i个物品(这种情况下,第i种物品一定是和第i-1个物品配对)， 10 则dp[i][j]=dp[i-2][j-1]+(w[i]-w[i-1])*(w[i]-w[i-1]) 11 dp[i][j]的j对也可能不含有第i个物品，此时有 12 dp[i][j]=dp[i-1][j] 13 状态转移方程 14 dp[i][j]=min{dp[i-2][j-1]+(w[i]-w[i-1])*(w[i]-w[i-1]),dp[i-1][j]} 15 */ 16 17 #include<iostream> 18 #include<algorithm> 19 const int N=2020; 20 const int inf=1100000000;//这个数据得大些，一开始wa了 21 using namespace std; 22 23 int w[N]; 24 int dp[N][N/2];//dp[i][j]表示前i个物品选j对的疲劳度 25 26 int main(){ 27 int n,k; 28 while(scanf("%d%d",&n,&k)!=EOF){ 29 for(int i=1;i<=n;i++){ 30 scanf("%d",&w[i]); 31 } 32 sort(w+1,w+n+1); 33 for(int i=0;i<=n;i++){ 34 for(int j=1;j<=2*i;j++){ 35 dp[i][j]=inf; 36 } 37 } 38 for(int i=0;i<=n;i++){ 39 dp[i][0]=0; 40 } 41 for(int i=2;i<=n;i++){ 42 for(int j=1;2*j<=i;j++){ 43 dp[i][j]=min(dp[i-1][j],dp[i-2][j-1]+(w[i]-w[i-1])*(w[i]-w[i-1])); 44 } 45 } 46 printf("%d\n",dp[n][k]); 47 } 48 return 0; 49 }