食用前注意自己加上第一步删除的边，此题解仅供参考
思路：
- DP题
- 环状结构通常处理方法：拆开复制两倍
- f[i][j][1]表示：删除i~j后的最大值，f[i][j][0]表示：删除i~j后的最小值
- 加法可直接有已完成状态最大值转移；而乘法则有四种可能，因为有负数存在
注意：
注意初始化最小最大值
#include <iostream>
#include <algorithm>
#include <cstdio>
#define inf 0x7fffffff
#define maxn 105
using namespace std;
int v[maxn],n,f[maxn][maxn][2];
char e[maxn];
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;++i) cin>>e[i]>>v[i];
for(int i=1;i<=2*n;++i)
for(int j=i+1;j<=2*n;++j) f[i][j][0]=inf;
for(int i=1;i<=2*n;++i)
for(int j=i+1;j<=2*n;++j) f[i][j][1]=-inf;
for(int i=1;i<=n;++i) e[i+n]=e[i],f[i+n][i+n][0]=f[i+n][i+n][1]=f[i][i][0]=f[i][i][1]=v[i];//复制两倍
for(int len=2;len<=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 a=f[i][k][0],b=f[k+1][j][0],c=f[i][k][1],d=f[k+1][j][1];
if(e[k+1]=='t')
{
f[i][j][0]=min(f[i][j][0],a+b);
f[i][j][1]=max(f[i][j][1],c+d);
}
if(e[k+1]=='x')
{
int s[4]={a*b,a*d,c*b,c*d};
sort(s,s+4);
f[i][j][0]=min(f[i][j][0],s[0]);
f[i][j][1]=max(f[i][j][1],s[3]);
}
}
}
int ans=0,left,right;
for(int i=1;i<=n;++i) ans=max(ans,f[i][i+n-1][1]);
//自加代码：第一步删除的边
printf("%d\n",ans);
}
马蜂不接受反驳，欢迎点赞
记录一下：博客 开通日期:2020/6/30
