hdu 1500 Chopsticks

http://acm.hdu.edu.cn/showproblem.php?pid=1500

dp[i][j]为第i个人第j个筷子。

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <algorithm>
 4 using namespace std;
 5 
 6 int dp[1011][5011];
 7 int a[5011];
 8 int k,n;
 9 int sqr(int x)
10 {
11     return x*x;
12 }
13 bool cmp(const int a,const int b)
14 {
15     return a>b;
16 }
17 
18 int main()
19 {
20     int t;
21     scanf("%d",&t);
22     while(t--)
23     {
24         scanf("%d%d",&k,&n);
25         memset(dp,0,sizeof(dp));
26         memset(a,0,sizeof(a));
27         for(int i=1; i<=n; i++)
28         {
29             scanf("%d",&a[i]);
30         }
31         sort(a+1,a+n+1,cmp);
32         k=k+8;
33         for(int i=1; i<=k; i++)
34         {
35             dp[i][i*3]=dp[i-1][i*3-2]+sqr(a[i*3-1]-a[i*3]);
36             for(int j=i*3+1; j<=n; j++)
37             {
38                 dp[i][j]=min(dp[i][j-1],dp[i-1][j-2]+sqr(a[j-1]-a[j]));
39             }
40         }
41         printf("%d
",dp[k][n]);
42     }
43     return 0;
44 }

View Code