题目链接: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<y) x=y;
} int dp[155][155]; void clear(int t)
{
int i,j,k;
for(i=1;i<12;i++) for(j=0;j<=n+1;j++) for(k=0;k<=n+1;k++) f[t][i][j][k]=-INF;
} int main()
{ n=getInt();
m=getInt();
int i,j,k;
for(i=1;i<=n;i++)
{
for(j=1;j<=m;j++) a[i][j]=getInt()+a[i-1][j];
}
col=1;
int pre=0,cur=1;
clear(pre);
for(i=1;i<=n;i++) for(j=i;j<=n;j++)
{
f[0][1][i][j]=S(i,j);
} int ans=-INF;
for(col=2;col<=m;col++)
{
clear(cur); //1
for(i=1;i<=n;i++) for(j=i;j<=n;j++)
{
upMax(f[cur][1][i][j],f[pre][1][i][j]+S(i,j));
upMax(f[cur][1][i][j],S(i,j));
} //2
for(i=1;i<=n;i++)
{
dp[i][n+1]=-INF;
for(j=n;j>=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<j;i++) upMax(dp[i+1][j],dp[i][j]);
for(i=1;i<=n;i++) for(j=i;j<=n;j++) upMax(dp[i][j+1],dp[i][j]);
for(i=1;i<=n;i++) for(j=i;j<=n;j++)
{
upMax(f[cur][2][i][j],dp[i][j]+S(i,j));
} //3
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=j;i>=1;i--) upMax(dp[i-1][j],dp[i][j]);
for(i=1;i<n;i++) for(j=i+1;j<=n;j++)
{
upMax(f[cur][3][i][j],dp[i+1][j]+S(i,j));
upMax(f[cur][3][i][j],f[pre][3][i][j]+S(i,j)); } //4
int tmp=f[pre][4][1][1]; for(i=1;i<=n;i++) for(j=i;j<=n;j++) upMax(tmp,f[pre][3][i][j]);
f[cur][4][1][1]=tmp; //5
for(i=1;i<=n;i++) for(j=i;j<=n;j++) if(j-i+1>=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);
}

最新文章

  1. uva 1001(最短路)
  2. docker学习笔记一:基本安装和设置容器静态ip
  3. SOME USEFUL MACHINE LEARNING LIBRARIES.
  4. 【C语言】4-指针
  5. Linux下使用cat制作“内涵图”
  6. iOS 静态库,动态库与 Framework 浅析
  7. Lua教程
  8. 提高GitHub下载速度
  9. python函数学习1
  10. 更新 Anaconda 库文件
  11. Spring Boot 2.0尝鲜-动态 Banner
  12. SDN 第四次上机作业
  13. 跟我一起学习ASP.NET 4.5 MVC4.0(一)
  14. sql row_number 用法
  15. JS-Zepto.js中文链接
  16. 001-hive是什么
  17. DataTable数据分页
  18. git branch --set-upstream hmyq/master master
  19. [DB2]Linux下安装db2 v9.7
  20. 2017.10.10 java中的继承与多态(重载与重写的区别)

热门文章

  1. java面向对象_构造器
  2. Web Service简介 内部资料 请勿转载 谢谢合作
  3. Linux环境部署(JDK/Tomcat/MySQL/证书)
  4. strstr函数的用法
  5. mysql replication principle--转
  6. OS初识
  7. Droidicon – 1600+ 漂亮的 Android 图标
  8. 【BZOJ】1019: [SHOI2008]汉诺塔
  9. HTTP 笔记与总结(7)HTTP 缓存(配合 Apache 服务器)
  10. 51Nod 算法马拉松15 记一次悲壮而又开心的骗分比赛
  11. ASP.NET MVC 表单的几种提交方式
  12. 国内云存储对比: 阿里云、腾讯云、Ucloud、首都在线
  13. CSS 预处理器中的循环
  14. 存储引擎-Buffered tree
  15. java中的线程池原理
  16. Centos 6 安装 Mysql 5.6
  17. 配置firewalld防火墙
  18. java中使用switch-case的用法及注意事项超全总结
  19. postgre 导出单表和导入
  20. 浅谈JS的变量提升