UVa 1366 DP Martian Mining
2024-08-30 09:15:58
网上的题解几乎都是一样的:
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 ;
}
代码君
最新文章
- HTML 或 CSS 文件中引用的图片文件移动到任意位置
- Java并发编程:synchronized
- eclipse svn
- java常用开发工具类之 图片水印,文字水印,缩放,补白工具类
- 函数式编程Map()&;Reduce()
- 【PHP操作sphinx】
- 如何将DJANGO轻量级化
- JS实现rgb与16进制颜色相互转换
- uboot使用tftp下载时出现“checksum bad”问题原因分析
- linux系统应用--Linux下用virtualBox安装win7(共享文件夹)
- ASP.NET WebForm
- JS判断页面加载是否完成
- Vue(二)简单入门
- Python 实现清屏
- 朱晔的互联网架构实践心得S1E9:架构评审一百问和设计文档五要素
- Ubuntu16.04安装最新版nodejs
- css小笔记
- MySQL 5.5加主键锁读问题【转载】
- 自学Java第四周的总结
- 通过plsql develop查看建表语句
热门文章
- Dev控件工具箱安装
- Android 模仿苹果虚拟悬浮按钮(自动靠边、可浮现任何界面上)
- (转)!注意:PreTranslateMessage弹出框出错
- mysql-练级查询
- Logback文档(1)
- vue 文件流下载xlsx 功能实现
- Problem N: 求二维数组中的鞍点【数组】
- 2018.4.22 深入理解Java的接口和抽象类
- WINDOWS-API:关于线程 GetCurrentThread、GetCurrentThreadId、GetCurrentProcess、GetCurrentProcessId
- css实现页面文字不换行、自动换行、强制换行