题面链接

https://www.acwing.com/problem/content/description/285/

思路

题目给出一个多边形，边为运算符，顶点为数值，所求为删去一条边之后，通过不断合并边可以获得的最大值。

乍一看，删去哪一条边获取最大值是未知的，需要枚举每一条边。

枚举之后，原来的多边形退化为一条链，问题变成一个类似石子合并（https://www.acwing.com/problem/content/284/）的问题，大致方向就是区间DP，阶段更新就是区间的长度。问题变为，如何确定满足无后效性以及最优子结构性质的状态。

由于运算符中存在乘法，故而不能将状态设计为最大值，因为一个负的最大值和一个正的最大值的乘积可能是一个很小的值。因此，还需要设计一个最小值状态，在乘法更新的时候，需要枚举最大值、最小值相乘的四种情况。

代码

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
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
#include <bits/stdc++.h>
using namespace std;

const int N = 55;
const int INF = 0x3f3f3f3f;
const int NINF = -0x3f3f3f3f;
const int ADD = 0;
const int MUL = 1;
int dp_max[N][N];
int dp_min[N][N];

int val[N];
int op[N];// 0-add, 1-mul


int solve(int start, int tot){
    
    for(int i=0;i<N;i++){
        for(int j=0;j<N;j++){
            dp_max[i][j]=NINF;
            dp_min[i][j]=INF;
        }
    }
    
    for(int len = 1;len<=tot;len++){
        for(int l=0;l+len-1<tot;l++){
            int r = l+len-1;
            
            int _l = (l+start)%tot;
            if (len==1){
                dp_max[l][r] = val[_l];
                dp_min[l][r] = val[_l];
                continue;
            }
            
            for(int k=l; k<r; k++){
                int _op = op[(k+1+start)%tot];
                if (_op==ADD){
                    dp_max[l][r] = max(dp_max[l][r], dp_max[l][k]+dp_max[k+1][r]);
                    dp_min[l][r] = min(dp_min[l][r], dp_min[l][k]+dp_min[k+1][r]);
                    continue;
                }
                
                if (_op==MUL){
                    int MM = dp_max[l][k]*dp_max[k+1][r];
                    int Mm = dp_max[l][k]*dp_min[k+1][r];
                    int mM = dp_min[l][k]*dp_max[k+1][r];
                    int mm = dp_min[l][k]*dp_min[k+1][r];
                    dp_max[l][r] = max(dp_max[l][r],max(MM,max(Mm,max(mM,mm))));
                    dp_min[l][r] = min(dp_min[l][r], min(MM,min(Mm,min(mM,mm))));
                }
            }
        }
    }
    return dp_max[0][tot-1];
}

int main(){
    int tot;
    cin>>tot;
    for(int i=0;i<tot;i++){
        char ch;
        cin>>ch;
        op[i] = (ch=='t')?ADD:MUL;
        cin>>val[i];
    }
    
    vector<int> ans_set;
    int max_val=NINF;
    for(int i=0;i<tot;i++){
        int tem_val = solve(i,tot);
        if(tem_val>max_val){
            max_val = tem_val;
            ans_set.clear();
            ans_set.push_back(i+1);
        }else if(tem_val == max_val){
            ans_set.push_back(i+1);
        }
    }
    cout<<max_val<<endl;
    for(auto i:ans_set){
        cout<<i<<" ";
    }
    cout<<endl;
    return 0;
}