(luogu4342)Polygon(IOI1998)

发表于 分类于 ，

原题链接

思路:

一眼看上去是个裸的区间 dp, 但是直接套石子合并的话会 WA.

由于乘法运算的存在，可能会有负负得正的情况出现， 所以记录最大值时同时要记录最小值.

然后状态转移方程中同时考虑两者即可.

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
#include <iostream>
#include <algorithm>
#include <climits>
using namespace std;
const int Mn(205);
long long an[Mn];   //数字
bool ao[Mn];        //符号, ao[i]表示i与i+1之间的符号
long long dp[Mn][Mn],dn[Mn][Mn];    //最大值与最小值(区间起点,区间长度)

int main() {
    ios::sync_with_stdio(false);
    int n;
    cin >> n;
    char op;
    cin >> op;  //先输入第一个运算符更方便处理
    ao[n] = (op=='x');
    for(int i(1);i<n;++i) {
        cin >> an[i] >> op;
        an[i+n] = an[i];    //"化环为链"
        ao[i+n] = ao[i] = (op=='x');    //同上
    }
    cin >> an[n];
    for(int i(1);i<2*n;++i) {
        dp[i][1] = dn[i][1] = an[i];    //初始化
    }
    for(int l(2);l<=n;++l) {    //枚举区间长度
        for(int i(1);i+l-1<2*n;++i) {   //枚举区间起点
            /*----状态转移----*/
            if(ao[i]) {
                dp[i][l] = max(dp[i+1][l-1] * an[i], dn[i+1][l-1] * an[i]);
                dn[i][l] = min(dp[i+1][l-1] * an[i], dn[i+1][l-1] * an[i]);
            } else {
                dp[i][l] = dp[i+1][l-1] + an[i];
                dn[i][l] = dn[i+1][l-1] + an[i];
            }
            for(int k(i+1);k<i+l-1;++k) {
                if(ao[k]) {
                    /*----乘法时由于"负负得正"需要考虑四种情况----*/
                    dp[i][l] = max(dp[i][l],dp[i][k-i+1] * dp[k+1][l-k+i-1]);
                    dp[i][l] = max(dp[i][l],dp[i][k-i+1] * dn[k+1][l-k+i-1]);
                    dp[i][l] = max(dp[i][l],dn[i][k-i+1] * dn[k+1][l-k+i-1]);
                    dp[i][l] = max(dp[i][l],dn[i][k-i+1] * dp[k+1][l-k+i-1]);
                    dn[i][l] = min(dn[i][l],dp[i][k-i+1] * dp[k+1][l-k+i-1]);
                    dn[i][l] = min(dn[i][l],dp[i][k-i+1] * dn[k+1][l-k+i-1]);
                    dn[i][l] = min(dn[i][l],dn[i][k-i+1] * dn[k+1][l-k+i-1]);
                    dn[i][l] = min(dn[i][l],dn[i][k-i+1] * dp[k+1][l-k+i-1]);
                } else {
                    /*----加法则不需要----*/
                    dp[i][l] = max(dp[i][l],dp[i][k-i+1] + dp[k+1][l-k+i-1]);
                    dn[i][l] = min(dn[i][l],dn[i][k-i+1] + dn[k+1][l-k+i-1]);
                }
            }
        }
    }
    /*----输出答案----*/
    long long ans(LONG_LONG_MIN);
    for(int i(1);i<=n;++i) {
        ans = max(ans,dp[i][n]);
    }
    cout << ans << endl;
    for(int i(1);i<=n;++i) {
        if(dp[i][n]==ans) {
            cout << i << " ";
        }
    }
    return 0;
}