欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

石子合并问题--直线版 HRBUST - 1818

程序员文章站 2022-05-29 10:09:07
t题目链接:https://vjudge.net/problem/HRBUST-1818 思路:一段已经合并的区间,分成两段区间,遍历所有能分开的区间。 代码有注释,基本就这样一个简单是思路。 ......

t题目链接:https://vjudge.net/problem/hrbust-1818

思路:一段已经合并的区间,分成两段区间,遍历所有能分开的区间。

代码有注释,基本就这样一个简单是思路。


 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <algorithm>
 5 #include <queue>
 6 #include <map>
 7 #include <cmath>
 8 #include <iomanip>
 9 using namespace std;
10 
11 typedef long long ll;
12 #define inf (1ll << 25)
13 #define rep(i,j,k) for(int i = (j); i <= (k); i++)
14 #define rep__(i,j,k) for(int i = (j); i < (k); i++)
15 #define per(i,j,k) for(int i = (j); i >= (k); i--)
16 #define per__(i,j,k) for(int i = (j); i > (k); i--)
17 
18 
19 const int n = 110;
20 int sum[n];
21 int dpma[n][n];
22 int dpmi[n][n];
23 
24 int main(){
25 
26     ios::sync_with_stdio(false);
27     cin.tie(0);
28 
29     int n;
30     while(cin >> n){
31 
32         rep(i,1,n) rep(j,1,n){
33             dpma[i][j] = 0;
34             dpmi[i][j] = inf;
35         }
36 
37         int in;
38         rep(i,1,n){
39             cin >> in;
40             sum[i] = sum[i - 1] + in;
41         }
42 
43         rep(i,1,n){
44             dpmi[i][i] = 0; //我这里直接从长度为2开始合并,然后遍历分区间
45         }
46 
47         rep(l,2,n){ //合并的区间长度
48             rep(i,1,n - l + 1){ //开始位置
49                 int e = i + l - 1; //结束为止
50                 rep(o,i,e - 1){ //分段位置
51                     int v = sum[e] - sum[i - 1];
52                     dpma[i][e] = max(dpma[i][e], dpma[i][o] + dpma[o + 1][e] + v);
53                     dpmi[i][e] = min(dpmi[i][e], dpmi[i][o] + dpmi[o + 1][e] + v);
54                 }
55             }
56         }
57 
58         cout << dpmi[1][n] << ' ' << dpma[1][n] << endl;
59     }
60 
61     getchar();getchar();
62 
63     return 0;
64 }