HDOJ 1421 搬寝室
中文题意很好理解，我们知道要想使疲惫度最小说明两只手拿的东西要尽量接近才能最小，所以先对物品的重量进行排序，我们即使要取也取相邻的物品，将相邻的物品的差的平方另外存储，就可以得到一个状态转移方程：dp[i][j]=min(dp[i-1][j],dp[i-2][j-1]+s[i]),
s[i]是代表i,i+1这两个物品的疲惫度.主要是因为s[i-1],s[i].代表的是ai-1,ai,ai+1的疲惫度，中间共享了一个ai，所以要dp[i-2].
代码：
#include<iostream>#include<algorithm>using namespace std;#define INF 0x7fffffff int dp[2000][2000],a[2000],s[2000];int main(){ int n,k,i,j; while( scanf("%d%d",&n,&k)!=EOF){ for( i=1; i<=n; i++) scanf("%d",&a[i]); sort(a,a+n+1); for( i=1; i<=n; i++) for( j=1; j<=n/2; j++) dp[i][j]=INF; for( i=2; i<=n; i++) s[i]=(a[i]-a[i-1])*(a[i]-a[i-1]); for( i=2; i<=n; i++) for( j=1; j<=i/2; j++) dp[i][j]=min(dp[i-1][j],dp[i-2][j-1]+s[i]); printf("%d\n",dp[n][k]); } return 0;}