算法课要求做多边形游戏，在acwing的OJ上认真水了一下

典型区间DP，首先来DP分析一下

已知i为区间左端点，j为区间右端点

对于加法：

和矩阵相乘一样，直接切分加起来即可
$ f[i][j] = max(f[i][j], f[i][k] + f[k + 1][j]) $
$ g[i][j] = min(g[i)[j], g[i][k] + g[k + 1][j]) $

对于乘法

这里要讨论四种情况
$ x1 = g[i][k] * g[k + 1][j] $ 左区间最小值乘右区间最小值
$ x2 = g[i][j] * f[k + 1][j] $ 左区间最小值乘右区间最大值
$ x3 = f[i][k] * g[k + 1][j] $ 左区间最大值乘右区间最小值
$ x4 = f[i][k] * f[k + 1][j] $ 左区间最大值乘右区间最大值
$ f[i][j] = max(f[i][j], max(x1, x2, x3, x4)) $
$ g[i][j] = min(f[i][j], min(x1, x2, x3, x4)) $

#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int N = 110, INF = 32768;
int n;//n边形
char c[N];//符号
int w[N];//顶点上的整数
int f[N][N], g[N][N];//存储max和min的集合
//f[i][j]为从区间[i,j]中所能合并取得的最高分
//g[i][j]为从区间[i,j]中所能合并取得的最低分
int main(){
    cin >> n;// n边形
    for(int i = 1; i <= n; i ++){
        cin >> c[i] >> w[i];//符号和顶点上的整数
        c[i + n] = c[i];//破环为链，确保每个点对（包括首尾）都能考虑到
        w[i + n] = w[i];
    }
    for(int len = 1; len <= n; len ++){//遍历区间长度
        for(int i = 1; i + len - 1 <= n * 2; i ++){//遍历左端点
            int j = i + len - 1;//得出右端点
            if(len == 1){//区间长度为1时
                f[i][j] = g[i][j] = w[i];//最大最小值就是这个数本身
            }else{//区间长度为2以上时
                f[i][j] = -INF, g[i][j] = INF;//初始化最大最小值
                for(int k = i; k < j; k ++){//开始切分
                    char op = c[k + 1];//取符号
                    int minI = g[i][k], maxI = f[i][k], minJ = g[k + 1][j], maxJ = f[k + 1][j];
                    if(op == 't'){//t代表加号
                        f[i][j] = max(f[i][j], f[i][k] + f[k + 1][j]);//maxI + maxJ
                        g[i][j] = min(g[i][j], g[i][k] + g[k + 1][j]);//minI + minJ
                    }else{//乘号
                    int x1 = minI * minJ, x2 = minI * maxJ, x3 = maxI * minJ, x4 = maxI * maxJ;
                        f[i][j] = max(f[i][j], max(max(x1, x2), max(x3, x4)));//x1~x4中取最大，进行更新
                        g[i][j] = min(g[i][j], min(min(x1, x2), min(x3, x4)));//x1~x4中取最小，进行更新
                    }
                }
            }
        }
    }
    int ans = -INF;
    for(int i = 1; i <= n; i ++) ans = max(ans, f[i][i + n - 1]);
    cout << ans << endl; //求出最高分数
    for(int i = 1; i <= n; i ++){
        if(ans == f[i][i + n - 1]){//求出最佳方案
            cout << i << ' ';
        }
    }
    return 0;
}