题意不再赘述。
这题和合并石子很类似，但是多了个乘法，而乘法是不满足“大大得大”的，因为两个非常小的负数乘起来也会很大，一个负数乘一个很大的整数会很小，所以我们需要添加一维状态，保存最大值和最小值。
\(f[i][j][0]\)表示第
\(i\)个到第
\(j\)个合并后的最大值，
\(f[i][j][1]\)表示最小值。如果是乘法，更新时用最大值和最小值都乘一遍就行了。
还有就是，破环成链复制一倍，这样就不用枚举砍掉哪条边了，如果结果是
\(f[1][n][0]\)，那么砍掉的肯定是
\(n-1\)这条边，以此类推。
总时间复杂度
\(O(n^3)\) #include #include using namespace std;#define INF 2147483647const int MAXN = 100;int n, f[MAXN << 1][MAXN << 1][3], a[MAXN], ans;char op[MAXN << 1];int main(){ cin >> n; cin >> op[n]; for(int i = 1; i < n; ++i) cin >> f[i][i][0] >> op[i], f[i][i][1] = f[i][i][0]; cin >> f[n][n][0], f[n][n][1] = f[n][n][0]; for(int i = n + 1; i <= (n << 1); ++i) //复制一倍 f[i][i][0] = f[i][i][1] = f[i - n][i - n][0], op[i] = op[i - n]; for(int l = 2; l <= n; ++l) //枚举长度 for(int i = 1; i <= (n << 1); ++i){ //枚举最短点 int j = i + l - 1; //算出右端点 f[i][j][1] = INF; //赋初值INF和-INF f[i][j][0] = -INF; for(int k = i; k < j; ++k){ //枚举中间数，更新答案 if(op[k] == 't') f[i][j][0] = max(f[i][j][0], f[i][k][0] + f[k + 1][j][0]), f[i][j][1] = min(f[i][j][1], f[i][k][1] + f[k + 1][j][1]); else f[i][j][0] = max(f[i][j][0], max(f[i][k][0] * f[k + 1][j][0], f[i][k][1] * f[k + 1][j][1])), f[i][j][1] = min(f[i][j][1], min(f[i][k][0] * f[k + 1][j][0], f[i][k][1] * f[k + 1][j][1])); } } for(int i = 1; i <= n; ++i) //记录砍掉哪些边可以得到最大答案 if(f[i][i + n - 1][0] > ans) ans = f[i][i + n - 1][0], a[a[0] = 1] = i; else if(f[i][i + n - 1][0] == ans) a[++a[0]] = i; printf("%d\n", ans); for(int i = 1; i <= a[0]; ++i) printf("%d ", a[i]); return 0;}