本文共 1529 字，大约阅读时间需要 5 分钟。
2 11 3
4
分析：首先以dp[n][k]，表示在n件物品只能选取k对的最优解，那么这种状态可以分为以下两种情况。
(1):第n件物品不搬，也就是在前n-1件物品中选取k对，疲劳值为dp[n-1][k]
(2):第n件物品要搬，那么相应的肯定是要搬第n-1件物品的，因为对于排序之后的序列，相邻两个数之差总是最小的。那么对应的就是在n-2件物品中搬k-1对，然后再加上第n-1对物品时的消耗，也就是n-1和n这一对。疲劳值为：
dp[n-2][k-1]+a[n-1]
所以状态转移方程自然就是两种情况取最小值即可；
即：dp[n][k]=min(dp[n-1][k]，dp[n-2][k-1]+a[n-1])；
当然还是要注意边界问题：
代码：
#include<bits/stdc++.h>
using namespace std; const int maxn=2005; const int INF=0x1f1f1f1f;//无穷大 int a[maxn]; int dp[maxn][maxn/2]; int work(int i,int j)//这里是判断边界问题 { if(j*2>i)//当你选取物品数大于总数时候，这种情况不发生 return INF; if(j==0)//一件物品都没搬过的时候，疲劳值为0 return 0; return dp[i][j]; } int main() { int n,k; while(scanf("%d%d",&n,&k)!=EOF) { memset(dp,0,sizeof(dp)); for(int i=1;i<=n;i++) { scanf("%d",&a[i]); } sort(a+1,a+n+1); for(int i=1;i<n;i++)//根据题意做一下预处理 { a[i]=a[i+1]-a[i]; a[i]*=a[i]; } for(int j=1;j<=k;j++)//枚举对数 { for(int i=2*j;i<=n;i++)//枚举物品数 { dp[i][j]=min(work(i-1,j),work(i-2,j-1)+a[i-1]); } } printf("%d\n",dp[n][k]); } return 0; }转载地址：http://pjncf.baihongyu.com/