# 多边形游戏

2023-08-29

#### 题意：

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

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

#### 代码：

#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.