Analysis

总体来说是一个区间DP

此题首先是一个环，要你进行删边操作，剩下的在经过运算得到一个最大值

注意事项:

1.删去一条边，剩下的构成一条线，相当于求此的最大值，经典区间DP该有的样子；

2.现在大概想法有了，还有一个细节，就是当中会出现负数，负数*负数是可能超过当前的最大值的，所以我们不仅需要维护区间最大值，还有最小值，因为两个极小值相乘是可以超过最大值的。

 1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<algorithm> 5 #define int long long  6 #define maxn 50+10 7 #define INF 9223372036854775807 8 using namespace std; 9 inline int read()  10 { 11 int x=0; 12 bool f=1; 13 char c=getchar(); 14 for(; !isdigit(c); c=getchar()) if(c==‘-‘) f=0; 15 for(; isdigit(c); c=getchar()) x=(x<<3)+(x<<1)+c-‘0‘; 16 if(f) return x; 17 return 0-x; 18 } 19 inline void write(int x) 20 { 21 if(x<0){putchar(‘-‘);x=-x;} 22 if(x>9)write(x/10); 23 putchar(x%10+‘0‘); 24 } 25 int n; 26 int sym[2*maxn],num[2*maxn]; 27 int dp[maxn][2*maxn][2*maxn],mdp[maxn][2*maxn][2*maxn]; 28 int ans; 29 inline int max_five(int a,int b,int c,int d,int e) 30 { 31 return max(max(max(a,b),max(c,d)),e); 32 } 33 inline int min_five(int a,int b,int c,int d,int e) 34 { 35 return min(min(min(a,b),min(c,d)),e); 36 } 37 inline void clear() 38 { 39 for(int i=1;i<=50;i++) 40  { 41 for(int j=1;j<=100;j++) 42  { 43 for(int k=1;k<=100;k++) 44  { 45 dp[i][j][k]=-INF; 46 mdp[i][j][k]=INF; 47  } 48  } 49  } 50 } 51 signed main() 52 { 53 // freopen("ploygon.in","r",stdin); 54 // freopen("ploygon.out","w",stdout); 55  clear(); 56 n=read(); 57 for(int i=1;i<=2*n;i++) 58  { 59 if(i%2==1)  60  { 61 char in; 62 cin>>in; 63 if(in==‘t‘) sym[i/2+1]=1; 64 else if(in==‘x‘) sym[i/2+1]=2; 65  } 66 else if(i%2==0) num[i/2]=read(); 67  } 68 for(int i=n+1;i<=2*n;i++)  69  { 70 sym[i]=sym[i-n]; 71 num[i]=num[i-n]; 72  } 73 for(int j=1;j<=n;j++) 74  { 75 for(int i=1;i<=2*n;i++) 76  { 77 dp[j][i][i]=num[i]; 78 mdp[j][i][i]=num[i]; 79  } 80  } 81 for(int i=1;i<=n;i++)  82  { 83 for(int len=2;len<=n;len++) 84  { 85 for(int j=i;j<=i+n-1;j++) 86  { 87 int k=j+len-1; 88 if(k>=i+n) break; 89 for(int l=j;l<k;l++) 90  { 91 if(sym[l+1]==1) 92  { 93 dp[i][j][k]=max(dp[i][j][k],dp[i][j][l]+dp[i][l+1][k]); 94 mdp[i][j][k]=min(mdp[i][j][k],mdp[i][j][l]+mdp[i][l+1][k]); 95  }  96 else if(sym[l+1]==2)  97  { 98 dp[i][j][k]=max_five(dp[i][j][k],dp[i][j][l]*dp[i][l+1][k],mdp[i][j][l]*dp[i][l+1][k],dp[i][j][l]*mdp[i][l+1][k],mdp[i][j][l]*mdp[i][l+1][k]); 99 mdp[i][j][k]=min_five(dp[i][j][k],dp[i][j][l]*dp[i][l+1][k],mdp[i][j][l]*dp[i][l+1][k],dp[i][j][l]*mdp[i][l+1][k],mdp[i][j][l]*mdp[i][l+1][k]);100  }101  }102  }103  }104 ans=max(ans,dp[i][i][i+n-1]);105  }106  write(ans);107 printf("\n");108 for(int k=1;k<=n;k++)109  {110 if(dp[k][k][k+n-1]==ans)111  {112  write(k);113 printf(" ");114  }115  }116 return 0;117 }

请各位大佬斧正（反正我不认识斧正是什么意思）