ZOJ 1234 UVA 10271 Chopsticks

这个题目，筷子应该最好是非降序排列的（只要输入的时候处理一下即可），这样处理起来就比较方便，因为这样就可以保证在后来的计算中，每取两个筷子都有比他们两根长的筷子，就可以符合题意了。

下面贴代码：

View Code

 1 #include <iostream>
 2 using namespace std;
 3 int dp[5050][1010];
 4 #define maxn 1<<30
 5 int a[5050];
 6 int main()
 7 {
 8 
 9     int ncase,guests,chopsticks,i,j;
10     cin>>ncase;
11     while(ncase--)
12     {
13         cin>>guests>>chopsticks;
14         for(i = chopsticks;i >= 1;i--)
15             cin>>a[i];
16         for(i = 1;i < 5050;i++)
17             for(j = 0;j < 1010;j++)
18             {
19                 if(j == 0)
20                     dp[i][j] = 0;
21                 else
22                     dp[i][j] = maxn;
23             }
24         for(j = 1;j <= guests + 8;j++)
25             for(i = 3;i <= chopsticks;i++)
26             {
27                 if(i >= j * 3)
28                 {
29                     dp[i][j] = dp[i - 1][j];
30                     int temp = dp[i - 2][j - 1] + (a[i - 1] - a[i]) * (a[i - 1] - a[i]);
31                     if(temp < dp[i][j])
32                         dp[i][j] = temp;
33                 }
34             }
35         cout<<dp[chopsticks][guests + 8]<<endl;
36     }
37     return 0;
38 }