题目链接：http://www.lydsy.com/JudgeOnline/problem.php?id=3241

题意：

思路：把每个字母分成三部分，两个字母之间还有空的列，所以我一共设了11个状态f[11][i][j]，123表示字母N，4表示NO之间的空列，567表示O，8表示OI之间的空列，9 10 11表示I。然后按照列DP.f[t][i][j]表示状态t，最上最下的位置[i,j]的最大价值。那么我们看转移：

1：直接生成或者从1转移过来

2：从1或者2转移过来

3：从2或者3转移过来

4：从3或者4转移过来

5：从4转移过来

6：从5或者6转移过来

7：从6转移过来

8：从7转移过来

9：从8或者9转移过来

10：从9或者10转移过来

11：从10或者11转移过来 并且这个状态可以更新答案

最麻烦的是从2状态向2状态转移。我们这里用我们正常的坐标，左上角为(1,1)。设转移为(2,k,t)->(2,i,j)，其中k<=i<=t+1,j>=t。我们将这个分成两种情况：

（1）i=t+1：设dp[t+1][t+1]=max(f[2][1][t],f[2][2][t],……,f[][2][t-1][t],f[2][t][t])。最后用dp[i][j]更新dp[i][j+1]，那么直接用dp[i][j]更新当前的f[2][i][j];

（2）k<=i<=t：比如k=2,t=6，那么这个可以更新

[2,6],[2,7],……,[2,n]

[3,6],[3,7],……,[3,m]

……

[6,6],[6,7],……,[6,n]

因此设dp[i][j]=f[2][i][j]，之后用dp[i][j]更新dp[i+1][j]，最后再用dp[i][j]更新dp[i][j+1]即可。这两个更新的顺序不能反。

int f[2][12][155][155];int n,m,a[155][555];  int col;  int S(int i,int j){    return a[j][col]-a[i-1][col];} void upMax(int &x,int y){    if(x
     
      =i;j--) dp[i][j]=max(dp[i][j+1],f[pre][1][i][j]);        }         for(i=1;i<=n;i++) for(j=i;j<=n;j++)        {            upMax(f[cur][2][i][j],dp[i][j+1]+S(i,j));        }         for(i=1;i<=n;i++) for(j=i;j<=n;j++) dp[i][j]=-INF;        for(i=1;i<=n;i++) for(j=i;j<=n;j++) upMax(dp[j+1][j+1],f[pre][2][i][j]);        for(i=1;i<=n;i++) for(j=i+1;j<=n;j++) upMax(dp[i][j],dp[i][j-1]);        for(i=1;i<=n;i++) for(j=i;j<=n;j++)        {            upMax(f[cur][2][i][j],dp[i][j]+S(i,j));        }                 for(i=1;i<=n;i++) for(j=i;j<=n;j++) dp[i][j]=f[pre][2][i][j];        for(j=1;j<=n;j++) for(i=1;i
      
       =1;i--) upMax(dp[i-1][j],dp[i][j]);        for(i=1;i
       
        =3)        {            upMax(f[cur][5][i][j],f[pre][4][1][1]+S(i,j));        }         //6        for(i=1;i<=n;i++) for(j=i;j<=n;j++) if(j-i+1>=3)        {            upMax(f[cur][6][i][j],f[pre][5][i][j]+S(i,i)+S(j,j));            upMax(f[cur][6][i][j],f[pre][6][i][j]+S(i,i)+S(j,j));        }         //7        for(i=1;i<=n;i++) for(j=i;j<=n;j++) if(j-i+1>=3)        {            upMax(f[cur][7][i][j],f[pre][6][i][j]+S(i,j));        }        //8        tmp=f[pre][8][1][1];        for(i=1;i<=n;i++) for(j=i;j<=n;j++) upMax(tmp,f[pre][7][i][j]);        f[cur][8][1][1]=tmp;         //9        for(i=1;i<=n;i++) for(j=i;j<=n;j++) if(j-i+1>=3)        {            upMax(f[cur][9][i][j],f[pre][8][1][1]+S(i,i)+S(j,j));            upMax(f[cur][9][i][j],f[pre][9][i][j]+S(i,i)+S(j,j));        }        //10        for(i=1;i<=n;i++) for(j=i;j<=n;j++) if(j-i+1>=3)        {            upMax(f[cur][10][i][j],f[pre][9][i][j]+S(i,j));            upMax(f[cur][10][i][j],f[pre][10][i][j]+S(i,j));        }        //11        for(i=1;i<=n;i++) for(j=i;j<=n;j++) if(j-i+1>=3)        {            upMax(f[cur][11][i][j],f[pre][10][i][j]+S(i,i)+S(j,j));            upMax(f[cur][11][i][j],f[pre][11][i][j]+S(i,i)+S(j,j));             ans=max(ans,f[cur][11][i][j]);        }         pre^=1;        cur^=1;    }     printf("%d\n",ans);}