给定一个多边形，边上有符号，为 \(+\) 或 \(\times\) ，点上有权值。先断掉一条边变成链，再在其他边上进行缩边，将两个点变为一个点，权值为两点做边上的运算。求最大值和最大值对应可能断掉的边。 \(n\leq 50\) 。
第一眼是区间DP裸题，确实也是，然后就给出了第一版程序（和环上的合并石子类似），然后就WA成80pts了，以为是小问题，结果调不出来了，看了一眼题解，才发现思路全错了。
若只有加法，就可以像合并石子一样只记录最大值，然而有乘法就不一样了。简单举个例子，有可能是两个极小的数相乘一样也能产生最大值，然后记录一个最小值，暴力区间DP， \(O(n^3)\) ，可过。
#include<bits/stdc++.h>
using namespace std;
int n;
int a[105],p[105],f[105][105],g[105][105];
int main(){
for(int i=1;i<=100;++i){
for(int j=1;j<=100;++j){
f[i][j]=-1e9;
g[i][j]=1e9;
}
}
scanf("%d",&n);
for(int i=1;i<=n;++i){
char c;
do{
c=getchar();
}while(c!='t' && c!='x');
if(c=='t'){
p[i-1]=1;
}
else{
p[i-1]=2;
}
scanf("%d",&a[i]);
}
for(int i=n;i<=2*n-1;++i){
p[i]=p[i-n];
}
for(int i=n+1;i<=2*n;++i){
a[i]=a[i-n];
}
for(int i=1;i<=2*n;++i){
f[i][i]=a[i];
g[i][i]=a[i];
}
for(int len=2;len<=n;++len){
for(int i=1,j=i+len-1;j<=2*n;++i,++j){
for(int k=i;k<=j-1;++k){
if(p[k]==1){
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{
f[i][j]=max(f[i][j],max(f[i][k]*f[k+1][j],max(g[i][k]*f[k+1][j],max(f[i][k]*g[k+1][j],g[i][k]*g[k+1][j]))));
g[i][j]=min(g[i][j],min(f[i][k]*f[k+1][j],min(g[i][k]*f[k+1][j],min(f[i][k]*g[k+1][j],g[i][k]*g[k+1][j]))));
}
}
}
}
int maxn=-1e9;
for(int i=1;i<=n;++i){
maxn=max(maxn,f[i][i+n-1]);
}
printf("%d\n",maxn);
for(int i=1;i<=n;++i){
if(maxn==f[i][i+n-1]){
printf("%d ",i);
}
}
}