題意：給定一多邊形，邊帶兩種運算符號，點帶權值。刪除一條邊后變成一條鏈，求這條鏈的最大值。可以任意刪除一條邊，任意修改運算順序。
解法：設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;
}