hdu1421_搬寝室

 1 #include<stdio.h>
 2 #include<algorithm>
 3 using namespace std;
 4 #define N 2100
 5 typedef long long LL;
 6 LL dp[N][N/2];        //dp[i][j]: 前 i 件中拿走j对最少疲劳度
 7 LL a[N];              //记录重量
 8 LL fun(LL i,LL j)     //一次性搬运第 i 件和第 j 件消耗的疲劳度
 9 {
10   return (a[j]-a[i])*(a[j]-a[i]);
11 }
12 LL min(LL a,LL b)
13 {
14   return a>b?b:a;
15 }
16 int main()
17 {
18   LL n,k;
19   while(scanf("%I64d%I64d",&n,&k)!=EOF)
20   {
21     for(LL i=1;i<=n;i++)
22     {
23       scanf("%I64d",&a[i]);
24     }
25     sort(a,a+n+1);  //关键的一步，排序，排完序以后每次拿走的某对就肯定是相邻的
26     for(LL i=0;i<=n;i++)
27       for(LL j=0;j<=n/2;j++)
28         dp[i][j]=10000000000000;
29     for(LL i=0;i<=n;i++)  //不管前几件，拿走0对疲劳度肯定为0
30       dp[i][0]=0;
31     dp[2][1]=fun(2,1);    //前两件取一对疲劳度固定
32     for(LL i=3;i<=n;i++)
33     {
34       for(LL j=1;j<=i/2;j++)
35       {
36         dp[i][j]=min(dp[i-1][j],dp[i-2][j-1]+fun(i-1,i));
37         //前i件取j件分两种情况：
38         //1.第i件不取：那么最佳情况为dp[i-1][j];
39         //2.第i件取走：那么第j件必然和第j-1件一起拿，那么最佳为dp[i-2][j-1]+fun(i-1,i)
40       }
41     }
42     printf("%I64d
",dp[n][k]);
43   }
44   return 0;
45 }