题意：给定n个物品，每个物品有重量，
从中选出m对，使得这m对物品重量差的平方和最小。
疲劳度：m对物品重量差的平方和
解题思路
先对n中物品的重量排序
令dp[i][j]表示前i个物品中选j对的最小疲劳度。
则dp[i][j]可能含有第i个物品(这种情况下,第i种物品一定是和第i-1个物品配对)，
则dp[i][j]=dp[i-2][j-1]+(a[i]-a[i-1])*(a[i]-a[i-1])
dp[i][j]的j对也可能不含有第i个物品，此时有
dp[i][j]=dp[i-1][j]
状态转移方程
dp[i][j]=min{dp[i-2][j-1]+(a[i]-a[i-1])*(a[i]-a[i-1]),dp[i-1][j]}
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<algorithm> 5 #include<stdlib.h> 6 #include<cmath> 7 using namespace std; 8 #define N 2006 9 #define inf 2147483646 10 int n,k; 11 int a[N]; 12 int dp[N][N];//dp[i][j]表示在前i个选出j对的最小值 13 int main() 14 { 15 while(scanf("%d%d",&n,&k)==2){ 16 for(int i=1;i<=n;i++){ 17 scanf("%d",&a[i]); 18 } 19 sort(a+1,a+1+n); 20 for(int i=0;i<=n;i++){ 21 for(int j=1;j<=k;j++){ 22 dp[i][j]=inf; 23 } 24 } 25 26 //dp[0][0]=0; 27 for(int i=2;i<=n;i++){ 28 for(int j=1;j*2<=i;j++){ 29 dp[i][j]=min(dp[i-2][j-1]+(a[i]-a[i-1])*(a[i]-a[i-1]),dp[i-1][j]); 30 } 31 } 32 printf("%d\n",dp[n][k]); 33 } 34 return 0; 35 }
原文：http://www.cnblogs.com/UniqueColor/p/5147074.html
