c/c++语言开发共享石子合并问题–直线版 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 }