poj 1185
题意：开始时有一个由$n$个顶点构成的多边形。每个顶点被赋予一个整数值，每条边被赋予一个运算符+或*。所有边依次用整数从$1$到$n$编号。游戏第$1$步，将一条边删除，随后$n-1$步按以下方式操作：
选择一条边$E$以及由$E$连接着的$2$个顶点$V_1$和$V_2$删除;
用一个新的顶点取代边$E$以及由$E$连接着的$2$个顶点$V_1$和$V_2$。将由顶点$V_1$和$V_2$的整数值通过边$E$上的运算得到的结果赋予新顶点;
最后，所有边都被删除。得分就是所剩顶点上的整数值。请求出这个最大的得分，以及达到的方式。
环断开一条边以后就成了链，就可以考虑DP了。我们发现简单的区间DP不满足最优子结构。和CF981D差不多，但是肯定可以改改然后还是用DP解。之前那题是改成存在性问题然后再判，这题因为负数不符合最优子结构，所以我们可以存最大值最小值转移就行了。
最大值可以从$max+max, max \cdot max$转移，而最小值可以从$min+min, min \cdot min, max \cdot min$得到。因为这些值的绝对值都是最值，所以最小值一定在这些里面。
我们断环将环复制一遍接在后面，然后每个位置开始的答案就是$[1,n], [2,n+1],…,[n, n - 1]$
1、区间DP的阶段是区间长度
2、区间DP最好用记忆化搜索写
3、数组不要开小了
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<vector>
#include<set>
#include<cmath>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double
#define fir first
#define sec second
#define mp make_pair
using namespace std;
namespace flyinthesky {
const int MAXN = 55, INF = 40000;
int n, a[MAXN * 2], hh[MAXN * 2], dp[MAXN * 2][MAXN * 2][2]; // dp[0] -> min, dp[1] -> max
void clean() {
}
int solve() {
clean();
scanf("%d", &n);
for (int i = 1; i <= n; ++i) {
char s[5]; scanf("%s%d", s, &a[i]);
hh[i] = (s[0] == 't' ? 0 : 1); // 0 加 1 乘
a[i + n] = a[i], hh[i + n] = hh[i];
}
for (int i = 0; i <= 2 * n + 2; ++i)
for (int j = 0; j <= 2 * n + 2; ++j) dp[i][j][0] = INF, dp[i][j][1] = -INF;
for (int i = 1; i <= 2 * n; ++i) dp[i][i][0] = dp[i][i][1] = a[i];
for (int len = 2; len <= 2 * 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 op = hh[k + 1];
if (op == 0) {
if (dp[i][k][1] != -INF && dp[k + 1][j][1] != -INF)
dp[i][j][1] = max(dp[i][j][1], dp[i][k][1] + dp[k + 1][j][1]);
}
if (op == 1) {
if (dp[i][k][1] != -INF && dp[k + 1][j][1] != -INF)
dp[i][j][1] = max(dp[i][j][1], dp[i][k][1] * dp[k + 1][j][1]);
if (dp[i][k][0] != INF && dp[k + 1][j][0] != INF)
dp[i][j][1] = max(dp[i][j][1], dp[i][k][0] * dp[k + 1][j][0]);
}
if (op == 0) {
if (dp[i][k][0] != INF && dp[k + 1][j][0] != INF)
dp[i][j][0] = min(dp[i][j][0], dp[i][k][0] + dp[k + 1][j][0]);
}
if (op == 1) {
if (dp[i][k][0] != INF && dp[k + 1][j][0] != INF)
dp[i][j][0] = min(dp[i][j][0], dp[i][k][0] * dp[k + 1][j][0]);
if (dp[i][k][1] != -INF && dp[k + 1][j][1] != -INF)
dp[i][j][0] = min(dp[i][j][0], dp[i][k][1] * dp[k + 1][j][1]);
if (dp[i][k][0] != INF && dp[k + 1][j][1] != -INF)
dp[i][j][0] = min(dp[i][j][0], dp[i][k][0] * dp[k + 1][j][1]);
if (dp[i][k][1] != -INF && dp[k + 1][j][0] != INF)
dp[i][j][0] = min(dp[i][j][0], dp[i][k][1] * dp[k + 1][j][0]);
}
}
}
}
int ans = -INF;
for (int i = 1; i <= n; ++i) if (dp[i][i + n - 1][1] > ans) ans = dp[i][i + n - 1][1];
printf("%d\n", ans);
for (int i = 1; i <= n; ++i) if (dp[i][i + n - 1][1] == ans) printf("%d ", i);
return 0;
}
}
int main() {
flyinthesky::solve();
return 0;
}
