hdu 1421 搬寝室

先对a[]按小到大排序.设:dp[i][j]表示前 i 个物品中搬 j
对的最少疲劳度.

1、当i==2*j时,dp[i][j]=dp[i-2][j-1]+(a[i]-a[i-1])^2
因为,当 (a1-a2)^2+(a3-a4)^2 <= (a1-a4)^2+(a3-a2)^2 ( a1<=a2<=a3<=a4 ).
2、当i>2*j时,dp[i][j]=min( dp[i-1][j] , dp[i-2][j-1]+(a[i]-a[i-1])^2 )

　　题目传送门

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<algorithm>
 4 using namespace std;
 5 int dp[2001][2001];
 6 int w[2001];
 7 int min(int a, int b)
 8 {
 9     return a<b?a:b;
10 }
11 int main()
12 {
13     int n,k,i,j;
14     while(scanf("%d%d",&n,&k)==2)
15     {
16         for(i=1;i<=n;i++)
17             scanf("%d",&w[i]);
18         sort(w+1,w+n+1);
19         for(i=0;i<=n;i++)
20             for(j=0;j<=k;j++)
21                 dp[i][j] = 0;
22         for(i=2;i<=n;i++)
23             for(j=1;j*2<=i;j++)
24             {
25                 if(i==2*j)
26                     dp[i][j] = dp[i-2][j-1] + (w[i]-w[i-1])*(w[i]-w[i-1]);
27                 else
28                     dp[i][j] = min(dp[i-1][j],dp[i-2][j-1]+(w[i]-w[i-1])*(w[i]-w[i-1]));
29             }
30         printf("%d\n",dp[n][k]);
31     }
32     return 0;
33 }

参考：http://blog.csdn.net/pygzx/article/details/7381833