网上的题解几乎都是一样的:

d(i, j, 0)表示前i行前j列,第(i, j)个格子向左运输能得到的最大值。

d(i, j, 1)是第(i, j)个格子向上运输能得到的最大值。

但是有一个很关键的问题没有解释:

某个格子中的A矿或者B矿一定有其中一种能够运出来吗?有没有可能这个格子没有修建管道,仅仅是为了给其他管道让路,使得总体取得最大值呢?

从题解的状态转移方程上来看,不会的。

自己YY了好久,也没有想到一个能严格证明的方法。。

 #include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std; const int maxn = + ; int A[maxn][maxn], B[maxn][maxn];
int d[maxn][maxn][]; int main()
{
int n, m;
while(scanf("%d%d", &n, &m) && n)
{
for(int i = ; i <= n; i++)
for(int j = ; j <= m; j++) scanf("%d", &A[i][j]);
for(int i = ; i <= n; i++)
for(int j = ; j <= m; j++) scanf("%d", &B[i][j]); for(int i = ; i <= n; i++)
for(int j = ; j <= m; j++) A[i][j] += A[i][j-], B[i][j] += B[i-][j]; for(int i = ; i <= n; i++)
for(int j = ; j <= m; j++)
{
d[i][j][] = max(d[i-][j][], d[i-][j][]) + A[i][j];
d[i][j][] = max(d[i][j-][], d[i][j-][]) + B[i][j];
}
printf("%d\n", max(d[n][m][], d[n][m][]));
} return ;
}

代码君

最新文章

  1. HTML 或 CSS 文件中引用的图片文件移动到任意位置
  2. Java并发编程:synchronized
  3. eclipse svn
  4. java常用开发工具类之 图片水印,文字水印,缩放,补白工具类
  5. 函数式编程Map()&amp;Reduce()
  6. 【PHP操作sphinx】
  7. 如何将DJANGO轻量级化
  8. JS实现rgb与16进制颜色相互转换
  9. uboot使用tftp下载时出现“checksum bad”问题原因分析
  10. linux系统应用--Linux下用virtualBox安装win7(共享文件夹)
  11. ASP.NET WebForm
  12. JS判断页面加载是否完成
  13. Vue(二)简单入门
  14. Python 实现清屏
  15. 朱晔的互联网架构实践心得S1E9:架构评审一百问和设计文档五要素
  16. Ubuntu16.04安装最新版nodejs
  17. css小笔记
  18. MySQL 5.5加主键锁读问题【转载】
  19. 自学Java第四周的总结
  20. 通过plsql develop查看建表语句

热门文章

  1. Dev控件工具箱安装
  2. Android 模仿苹果虚拟悬浮按钮(自动靠边、可浮现任何界面上)
  3. (转)!注意:PreTranslateMessage弹出框出错
  4. mysql-练级查询
  5. Logback文档(1)
  6. vue 文件流下载xlsx 功能实现
  7. Problem N: 求二维数组中的鞍点【数组】
  8. 2018.4.22 深入理解Java的接口和抽象类
  9. WINDOWS-API:关于线程 GetCurrentThread、GetCurrentThreadId、GetCurrentProcess、GetCurrentProcessId
  10. css实现页面文字不换行、自动换行、强制换行