题目大意：

有一个n个点的环，每条边上有加号或乘号，然后这条边所连的两个点的权值就依据这条边上的符号来进行运算，将运算的结果作为一个新的节点。

问先去掉一条边，最后将所有边都进行运算，最后得到的最终点的权值最大是多少（输入时t表示该边为加号，x表示该边为乘号

思路：

首先分析题目可以看出应为dp。题目要求删除一条边后的最大得分，那么我们只要求出来从第i个顶点到第i-1个顶点（走一大圈）的最大分数就好了

可以想到列dp[i][k]表示以第i个顶点为起点顺时针走k个顶点的最大得分。（k>=1）

可以枚举分割点求出dp[i][k],又因为是一个环，枚举分割点较为麻烦，因此枚举分割长度j:

得到dp方程 dp[i][j]与dp[i+j][k-j]之间运算（1<=j<k）

但是有一个问题 因为存在负数，所以可能有两个负数相乘得到最大值

因此我们还需要求出以第i个顶点为起点顺时针走k个顶点的最小得分

这样就用两个数组maxf，minf记录一下

其中minf中两个乘的情况有些麻烦：求五个情况的最小值(minf[i][len],minf[i][j]*minf[(i+j)%n][len-j],minf[i][j]*maxf[(i+j)%n][len-j],maxf[i][j]*maxf[(i+j)%n][len-j],maxf[i][j]*minf[(i+j)%n][len-j])

最后搞一下长度为n就好了

 

1 #include
      
        2 #include
       
         3 #include
        
          4 #include
         
           5 #include
          
            6 #include
           
             7 #include
            
              8 #include
             
               9 #include
              
               10 #define MAXN 5511 using namespace std;12 bool edge[MAXN];13 char ch;14 int ans,maxf[55][55],minf[55][55],a,n;15 int main()16 {17 scanf("%d",&n);18 for(int i=0;i
               
                >ch>>a;23 if(ch=='t') edge[i]=true;24 maxf[i][1]=minf[i][1]=a;25 }26 for(int len=2;len<=n;len++)27 {28 for(int i=0;i