P1880 [NOI1995]石子合并

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 const int maxn = 205;
 4 const int inf = 0x3f3f3f3f;
 5 int cost1[maxn][maxn], cost2[maxn][maxn];  //当前合并的代价
 6 int dp1[maxn][maxn], dp2[maxn][maxn];
 7 int main() {
 8     int n; cin >> n;
 9     for (int i = 1; i <= n; i++) {
10         cin >> cost1[i][i];
11         cost2[i][i] = cost1[i][i];
12     }
13     for (int i = 1; i <= n; i++) {
14         cost1[n+i][n+i] = cost1[i][i];
15         cost2[n+i][n+i] = cost2[i][i];
16     }
17     n <<= 1;
18     for (int i = 2; i <= n/2; i++) {
19         for (int j = 0; j <= n-i; j++) {
20             int x = i+j, y = j+1;
21             for (int k = 1; k < i; k++) {
22                 cost1[x][y] = cost1[x-k][y] + cost1[x][y+i-k];
23                 cost2[x][y] = cost2[x-k][y] + cost2[x][y+i-k];
24                 if (dp1[x][y]) dp1[x][y] = min(dp1[x][y],cost1[x][y]+dp1[x-k][y]+dp1[x][y+i-k]);
25                 else dp1[x][y] = cost1[x][y]+dp1[x-k][y]+dp1[x][y+i-k];
26                 if (dp2[x][y]) dp2[x][y] = max(dp2[x][y],cost2[x][y]+dp2[x-k][y]+dp2[x][y+i-k]);
27                 else dp2[x][y] = cost2[x][y]+dp2[x-k][y]+dp2[x][y+i-k];
28             }
29         }
30     }
31     int mi = inf, mx = 0;
32     n >>= 1;
33     for(int j = 0; j <= n; j++) {
34         mi = min(mi,dp1[n+j][j+1]);
35     }
36     for(int j = 0; j <= n; j++) {
37         mx = max(mx,dp2[n+j][j+1]);
38     }
39     cout << mi << endl << mx << endl;
40 }