算法竞赛进阶指南， 284 页， 区间DP
题目意思：
有 n个点，每点都有一个整数（正，负， 0都可能）， 用 n 条边把 n个点连成一个环形， 每条边上
都有一个运算符（加号 或者 乘号）。现在任意删除一条边，剩下 n - 1 条边。加下来 进行 n - 1 步骤，每一步 ，玩家选择一条边，然后用该边两边的数值和边上的运算符运算，等到新的整数。然后替换原来的两个顶点和一条边。 依次操作，直到剩下最后一点。求这个数的最大值，还要输出，具体删除了哪些边能得到最大值（多个的话，按递增输出）
本题要点：
1、转态表示， f[L][R] 表示第 L个顶点到 第R个顶点合并为一个顶点后的最大值
g[L][R] 表示第 L个顶点到 第R个顶点合并为一个顶点后的最小值
2、转态转移：
因为两个区间的合并， 操作符可能是 加号 ‘+’ ，乘号 ‘’.
1) 如果操作符是 ‘+’
区间 [L, R]的最大值 = 左区间 [L, K] 的最大值 + 右区间 [K + 1, R] 的最大值 ;
区间 [L, R]的最小值 = 左区间 [L, K] 的最小值 + 右区间 [K + 1, R] 的最小值
2) 如果操作符是 '’
minL 表示 左区间 [L, K] 的最小值，
maxL 表示 左区间 [L, K] 的最大值
minR 表示 右区间 [K + 1, R] 的最小值，
maxR 表示 右区间 [K + 1, R] 的最大值
区间 [L, R]的最大值 = max{minL * minR, minL * maxR, maxL * minR, maxL * maxR}
区间 [L, R]的最大值 = min{minL * minR, minL * maxR, maxL * minR, maxL * maxR}注意K 的取值范围 L <= K < R
3、 注意， “破环成链” 的方法:
开两倍的区间来模拟 环形
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
using namespace std;const int MaxN = 110, INF = 0x3f3f3f3f;
char op[MaxN];
int ver[MaxN];
int n;
int f[MaxN][MaxN]; // f[L][R] 表示第 L个顶点到 第R个顶点合并为一个顶点后的最大值
int g[MaxN][MaxN]; // g[L][R] 表示第 L个顶点到 第R个顶点合并为一个顶点后的最小值
int remove_edge[MaxN];
int remove_cnt;int sort_4(int a, int b, int c, int d, int flag)
{
int num[4];num[0] = a, num[1] = b, num[2] = c, num[3] = d;sort(num, num + 4);if(flag == 1) //返回最大值{
return num[3];}return num[0];
}void solve()
{
for(int i = 1; i <= 2 * n; ++i){
for(int j = 1; j <= 2 * n; ++j){
f[i][j] = -INF, g[i][j] = INF;}}for(int i = 1; i <= 2 * n; ++i){
f[i][i] = g[i][i] = ver[i];}for(int len = 2; len <= n; ++len) //步长{
for(int i = 1; i + len - 1 < n * 2; ++i){
int j = i + len - 1; //右端点for(int k = i; k < j; ++k){
char c = op[k + 1];if(c == 't')//相加{
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]);}else{
int a = g[i][k] * g[k + 1][j], b = g[i][k] * f[k + 1][j], c = f[i][k] * g[k + 1][j], d = f[i][k] * f[k + 1][j]; f[i][j] = max(f[i][j], sort_4(a, b, c, d, 1)); g[i][j] = min(g[i][j], sort_4(a, b, c, d, 0));}}
// printf("f[%d][%d] = %d\n", i, j, f[i][j]);}}int ans = -INF;for(int i = 1; i <= n; ++i){
ans = max(ans, f[i][i + n - 1]); }printf("%d\n", ans);//所有去除这个边得到的最大值remove_cnt = 0;for(int i = 1; i <= n; ++i){
if(ans == f[i][i + n - 1]){
remove_edge[remove_cnt++] = i;}}for(int i = 0; i < remove_cnt; ++i){
printf("%d", remove_edge[i]);if(i + 1 < remove_cnt){
printf(" ");}else{
printf("\n");}}
}int main()
{
char ch[2] = {
0};scanf("%d", &n);for(int i = 1; i <= n; ++i){
scanf("%s%d", ch, &ver[i]);op[i] = op[n + i] = ch[0];ver[n + i] = ver[i];}solve();return 0;
}/* 4 t -7 t 4 x 2 x 5 *//* 33 1 2 */