题意：有n个点构成的环，环上的边t代表+，x代表*，选择先断一条边，然后问能获取最大值的方案和最大值。 思路：一开始想的是dp[l][r]代表l~r之间运算出来的最大值，结果发现不太行，因为l到r之间的数可能是负数，负数乘以负数可能会更新最大值那么我们多开一维记录最大值和最小值。最后就是细节问题了，我们可以枚举选哪一条边那复杂度就是on4了，还有另外一种做法也是区间dp的通用技巧，就是扩大一倍数组，可以有效降低到on3。昨天因为dp[i][j][0]=min(dp[i][k][0]+dp[k+1][j][0],dp[i][j][0]);这个部分没有和自身取min 样例都过不了难受死我
#include<bits/stdc++.h> using namespace std; const int mod=1e9; typedef long long ll; ll dp[110][110][2]; int n; ll a[110]; char g[110]; int main() { cin >> n; for(int i=1;i<=2*n;i++) { if(i%2==0) cin>>a[i/2],a[i/2+n]=a[i/2]; else cin >> g[i/2+1],g[i/2+n+1]=g[i/2+1]; } for(int i=1;i<=2*n;i++) dp[i][i][0]=dp[i][i][1]=a[i]; for(int len=2;len<=n;len++) for(int i=1;i+len-1<=2*n;i++) { int j=i+len-1; for(int k=l;k<=r-1;k++) { if(g[k]=='t') { dp[i][j][0]=min(dp[i][k][0]+dp[k+1][j][0],dp[i][j][0]); dp[i][j][1]=max(dp[i][k][1]+dp[k+1][j][1],dp[i][j][1]) } else { dp[i][j][0]=min(dp[i][k][0]*dp[k+1][j][1],dp[i][k][1]*dp[k+1][j][0]); dp[i][j][0]=min(dp[i][k][0]*dp[j][k][1],dp[i][j][0]); dp[i][j][1]=max(dp[i][k][0]*dp[k+1][j][0],dp[i][k][1]*dp[k+1][j][1]); } } } }