单路径最大和问题，设f[i][j][S]表示到达(i,j)，轮廓线状态为S的最优解。

S用4进制m+1位数表示，0表示无插头，1表示左括号，2表示右括号，3表示独立插头。

在DP之前先进行一次预处理，剔除无效状态，并预处理出与每个括号匹配的另一个括号的位置，有效状态只有8000个左右。

然后分类讨论进行转移即可。

 

#include
     
      const int N=9,M=8320,inf=-1000000000;int n,m,S,i,j,k,h,z,ans=inf,q[M],id[1<<(N*2)],pre[M],now[M];char can,c3,st[N+1],p[M][N],tmp[N];inline int bit(int x,int i){return x>>(i<<1)&3;}inline void up(int&a,int b){if(a
      
       2){can=0;break;}    }    if(can&&!st[0]){      q[id[i]=++q[0]]=i;      for(j=0;j<=m;j++)p[q[0]][j]=tmp[j];    }  }  clr();  now[1]=0;  nxt();  for(i=1;i<=n;i++){    clr();    for(k=1;k<=q[0];k++)if(pre[k]>inf&&!bit(q[k],m))now[id[q[k]<<2]]=pre[k];    nxt();    for(j=1;j<=m;j++){      scanf("%d",&z),up(ans,z),clr();      for(h=1;h<=q[0];h++)if(pre[h]>inf){        int v=pre[h]+z,k=q[h],x=bit(k,j-1),y=bit(k,j),e=k^(x<<((j-1)<<1))^(y<<(j<<1));        if(!x&&!y){          up(now[h],v-z);          up(now[id[e^(1<<((j-1)<<1))^(2<<(j<<1))]],v);          up(now[id[e^(3<<((j-1)<<1))]],v);          up(now[id[e^(3<<(j<<1))]],v);        }else if(!x||!y){          int t=x+y;          up(now[id[e^(t<<((j-1)<<1))]],v);          up(now[id[e^(t<<(j<<1))]],v);          if(t==3){if(!e)up(ans,v);}          else{            if(x)up(now[id[e^(x<<(p[h][j-1]<<1))]],v);            else up(now[id[e^(y<<(p[h][j]<<1))]],v);          }        }else if(x==1&&y==1)up(now[id[e^(3<<(p[h][j]<<1))]],v);        else if(x==2&&y==1)up(now[id[e]],v);        else if(x==2&&y==2)up(now[id[e^(3<<(p[h][j-1]<<1))]],v);        else if(x==3&&y==3){if(!e)up(ans,v);}        else if(x==3)up(now[id[e^(y<<(p[h][j]<<1))]],v);        else if(y==3)up(now[id[e^(x<<(p[h][j-1]<<1))]],v);      }      nxt();    }  }  return printf("%d",ans),0;}