题意：给定一多边形，边带两种运算符号，点带权值。删除一条边后变成一条链，求这条链的最大值。可以任意删除一条边，任意修改运算顺序。
解法：设dp[i][j]表示这条链上从i到j段的最大值，那么它可以分为两段来求,dp[i][k],dp[k+1][j],当它们之间是'+'号时，问题的求解也是最大值，但若为'*'号，子问题就不一定为最大值了，因为两个负数越小，相乘结果越大，所以要加一维,用dp[i][j][0]表示i到j段的最小值，dp[i][j][1]表示最大值，具体转移方程见代码。最后就是枚举删除的边，保存最大的链值就可以了。
#include <stdio.h>
#include <string.h>
#define N 55
#define INF 1 << 29
#define MIN(a, b) (a < b ? a : b)
#define MAX(a, b) (a > b ? a : b)
int DP(char op[][5], int v[], int n)
{
int dp[N][N][2];
for(int i = 0; i < n; i++)
dp[i][i][0] = dp[i][i][1] = v[i];
for(int j = 1; j < n; j++)
{
for(int i = j - 1; i >= 0; i--)
{
dp[i][j][0] = INF;
dp[i][j][1] = -INF;
for(int k = i; k < j; k++)
{
if(!strcmp(op[k], "t"))
{
dp[i][j][0] = MIN(dp[i][j][0], dp[i][k][0] + dp[k + 1][j][0]);
dp[i][j][1] = MAX(dp[i][j][1], dp[i][k][1] + dp[k + 1][j][1]);
}
else
{
dp[i][j][0] = MIN(dp[i][j][0], dp[i][k][0] * dp[k + 1][j][0]);
dp[i][j][0] = MIN(dp[i][j][0], dp[i][k][0] * dp[k + 1][j][1]);
dp[i][j][0] = MIN(dp[i][j][0], dp[i][k][1] * dp[k + 1][j][0]);
dp[i][j][1] = MAX(dp[i][j][1], dp[i][k][0] * dp[k + 1][j][0]);
dp[i][j][1] = MAX(dp[i][j][1], dp[i][k][1] * dp[k + 1][j][1]);
}
}
}
}
return dp[0][n - 1][1];
}
int main()
{
int n, t, ans[N], mmax;
char op[N][5], OP[N][5];
int v[N], V[N];
while(~scanf("%d", &n))
{
for(int i = 0; i < n; i++)
scanf("%s %d", &op[i], &v[i]);
mmax = -INF;
for(int k = 0; k < n; k++)
{
for(int i = 0; i < n; i++)
{
strcpy(OP[i], op[(i + k + 1) % n]);
V[i] = v[(i + k) % n];
// printf("%s %d ", OP[i], V[i]);
}
// printf("\n");
ans[k] = DP(OP, V, n);
if(ans[k] > mmax) mmax = ans[k];
}
printf("%d\n", mmax);
for(int i = 0; i < n; i++)
if(ans[i] == mmax)
{
printf("%d ", i + 1);
}
printf("\n");
}
return 0;
}