题目链接：
状态转移方程有点困难。。。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 18 #include 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 }