一道区间dp题，不少细节。
一开始我想定义f[i][j]表示区间[i,j]通过某种合并之后的最大值，之后这道题就等同于“NOI1995石子合并”。
但是转念一想，这道题有加法和乘法两种运算，如果单看加法，以上思路正确。但是因为乘法的存在，两个较小的数（负数）相乘或许会大于两个最大数相乘，因此以上思路在这里出现了错误。
因此，我们定义maxx[i][j],minn[i][j]分别表示区间[i,j]通过某种合并之后的最大值、最小值。
1、如果当前枚举决策为k，而且运算符为加号，则有
maxx[i][j]=max(maxx[i][k-1]+maxx[k][j]);
minn[i][j]=min(minn[i][k-1]+minn[k][j]);
如果运算符为乘号，则有
maxx[i][j]=max(maxx[i][k-1]*maxx[k][j]);
maxx[i][j]=max(minn[i][k-1]*minn[k][j]);
minn[i][j]=min(maxx[i][k-1]*maxx[k][j]);
minn[i][j]=min(minn[i][k-1]*minn[k][j]);
minn[i][j]=min(maxx[i][k-1]*minn[k][j]);
minn[i][j]=min(minn[i][k-1]*maxx[k][j]);
因此正确的算法就得出来了，我们枚举起始的位置开始计算即可，时间复杂度为O(n4).
在这里我们将这个环拆开并复制一倍，然后在这个两倍长的链上做一次dp，最后枚举起点选出答案即可，时间复杂度为O(n3).
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 using namespace std; 5 int n,maxx[60<<1][60<<1],minn[60<<1][60<<1],a[60<<1]; 6 char op[60<<1]; 7 int main() { 8 cin>>n; 9 memset(minn,0x3f,sizeof(minn)); 10 memset(maxx,-0x3f,sizeof(maxx)); 11 for(int i=1;i<=n;i++) { 12 char x; 13 int y; 14 cin>>x>>y; 15 a[i]=a[i+n]=y; 16 op[i]=op[i+n]=x; 17 } 18 for(int i=1;i<=n<<1;i++) 19 maxx[i][i]=minn[i][i]=a[i]; 20 for(int i=2;i<=n;i++) { 21 for(int l=1;l+i-1<=2*n;l++) { 22 for(int k=l+1;k<=l+i-1;k++) { 23 if(op[k]=='t') { 24 maxx[l][l+i-1]=max(maxx[l][l+i-1],maxx[l][k-1]+maxx[k][l+i-1]); 25 minn[l][l+i-1]=min(minn[l][l+i-1],minn[l][k-1]+minn[k][l+i-1]); 26 } 27 else { 28 maxx[l][l+i-1]=max(maxx[l][l+i-1],maxx[l][k-1]*maxx[k][l+i-1]); 29 maxx[l][l+i-1]=max(maxx[l][l+i-1],minn[l][k-1]*minn[k][l+i-1]); 30 minn[l][l+i-1]=min(minn[l][l+i-1],maxx[l][k-1]*maxx[k][l+i-1]); 31 minn[l][l+i-1]=min(minn[l][l+i-1],minn[l][k-1]*minn[k][l+i-1]); 32 minn[l][l+i-1]=min(minn[l][l+i-1],maxx[l][k-1]*minn[k][l+i-1]); 33 minn[l][l+i-1]=min(minn[l][l+i-1],minn[l][k-1]*maxx[k][l+i-1]); 34 } 35 } 36 } 37 } 38 int ans=-0x7fffffff; 39 for(int i=1;i<=n;i++) 40 ans=max(ans,maxx[i][i+n-1]); 41 cout<<ans<<endl; 42 for(int i=1;i<=n;i++) 43 if(ans==maxx[i][i+n-1]) cout<<i<<" "; 44 return 0; 45 }