题意：

1.游戏第1步，将一条边删除
2.后续步骤按以下方式操作：

• 选择一条边$E$以及由$E$连接着的$2$个顶点$V1$和$V2$；
• 用一个新的顶点取代边$E$以及由$E$连接着的$2$个顶点$V1$和$V2$。将由顶点$V1$和$V2$的整数值通过边$E$上的运算得到的结果赋予新顶点。

最后，所有边都被删除，游戏结束。游戏的得分就是所剩顶点上的整数值。求最大得分。

分析：

状态表示： $F[i][j][k]$：从$i$节点断开，往后$j$个节点的最大值和最小值（根据$k$值01区分最值）
状态计算：

代码：

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#define INF 0x7fffff
using namespace std;
const int N = 105;

int n;
int v[N];
char op[N];
int f[N][N][2];
int ans;

void dp() {
	for (int len = 2; len <= n; len ++) {
		for (int i = 1; i <= 2 * n - len + 1; i ++) {
			int j = i + len - 1;
			for (int k = i; k < j; k ++) {
				int a = f[i][k][0];
				int b = f[i][k][1];
				int c = f[k + 1][j][0];
				int d = f[k + 1][j][1];
				if (op[k + 1] == 't') {
					f[i][j][0] = max(f[i][j][0], a + c);
					f[i][j][1] = min(f[i][j][1], b + d);
				} else {
					f[i][j][0] = max(f[i][j][0], max(a*c,b*d));
					f[i][j][1] = min(f[i][j][1], min(b*d,min(a*d,b*c)));
				}
			}
		} 
	}
}

int main() {
	cin >> n;
	for (int i = 1; i <= n; i ++) {
		cin >> op[i] >> v[i]; 
	}
	//初始化 
	for(int i = 1; i <= 2 * n; i ++) {
		for (int j = i; j <= 2 * n; j ++) {
			f[i][j][0] = -INF;
			f[i][j][1] = INF;
		}
	}
	for (int i = 1; i <= n; i ++) {
		f[i][i][0] = v[i];
		f[i][i][1] = v[i];
		f[i + n][i + n][0] = v[i];
		f[i + n][i + n][1] = v[i];
		op[i + n] = op[i];
	}
	//dp
	dp(); 
	ans = -INF; 
	for (int i = 1; i <= n; i ++) 
		ans = max(ans, f[i][i + n - 1][0]);
	cout << ans << endl;
	for(int i = 1; i <= n; i++) {
		if(f[i][i + n - 1][0] == ans)
			cout << i << " ";
	}
	return 0;
}

题目链接：多边形游戏

Q.E.D.