xth 的玫瑰花(codevs 1360)
题目描述 Description
这天是rabbit 的生日前夕,Xth 来到花店,要给他的rabbit 买玫瑰花,为了保证质
量,他跟花店老板——小菜儿同学要求自己到花田采摘。小菜儿灰常希望早日见到
暖熊(xth 儿子的小名),于是他决定帮忙。
小菜儿告诉xth,花田是一个n ∗ m的矩形区域,里面有红玫瑰和黑玫瑰两种玫瑰。
Xth 探明了每一块小区域内红玫瑰和黑玫瑰的种植量,并且还在花田的北边和西边
分别设置了红玫瑰和黑玫瑰的收集站(地图上上北下南左西右东)。你的任务是设
计一个运输线系统,使得运送的红玫瑰和黑玫瑰的总量最多。
运输线有两种,一种是东西向,一种是南北向。在一个格子内你能建造一种运输线,
但不能两种都建。如果两个同类型运输线首尾相接,它们就可以被连接起来。
另外,这些玫瑰都十分不稳定,因此它们在运送过程中都不能拐弯。这就意味着如
果某个格子上建有南北向运输线,但是它北边的格子建有东西向运输线。那么这条
南北向运输线内运送的任何东西都将丢失。进一步地,运到红玫瑰收集点的黑玫瑰
会丢失,运到黑玫瑰收集点的红玫瑰也会丢失。
输入描述 Input Description
第一行包含两个整数n和m,表示花田大小。
以下n行,每行m个整数,其中第i行
第j个整数g[ i ,j ] 描述各个格子上的黑玫瑰数量。接下来以类似的矩阵表示各个格
子上的红玫瑰数量。
输出描述 Output Description
仅一个整数, 表示最多可以采集到的红玫瑰和黑玫瑰的总量。
样例输入 Sample Input
4 4
0 0 10 9
1 3 10 0
4 2 1 3
1 1 20 0
10 0 0 0
1 1 1 30
0 0 5 5
5 10 10 10
样例输出 Sample Output
98
数据范围及提示 Data Size & Hint
对于30%的数据: 0 ≤
n, m ≤ 100;
对于100%的数据: 0 ≤ n,m ≤ 1000;
0 ≤ g[ i,j ] ≤ 1000.
/*
由于管道不能交叉,所以如果想向北运,那么它南边的管道都要向北运,向西运也同理。
用a、b数组做个前缀和,转移时f[i][j]为它向北运和向西运的情况取大。
*/
#include<cstdio>
#include<iostream>
#define M 1010
using namespace std;
int a[M][M],b[M][M],f[M][M],n,m;
int main()
{
scanf("%d%d",&n,&m);
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++)
scanf("%d",&a[i][j]);
for(int i=;i<=n;i++)
for(int j=;j<=m;j++)
a[i][j]+=a[i-][j];
for(int i=;i<=n;i++)
for(int j=;j<=m;j++)
b[i][j]+=b[i][j-];
for(int i=;i<=n;i++)
for(int j=;j<=m;j++)
f[i][j]=max(f[i][j-]+a[i][j],f[i-][j]+b[i][j]);//保证不交叉
printf("%d",f[n][m]);
return ;
}
最新文章
- .net 大型分布式电子商务架构说明
- [django]windows下用Django,静态文件请求失败,出现UnicodeDecodeError
- frag General URL components
- Java/Android引用类型及其使用分析
- 注入问题0x00
- cocos2dx中CC_CALLBACK_1等宏中this指针实际指向
- 第十四篇:在SOUI中使用定时器
- 笔记本_thinkpad_e440
- ModalDialog.js
- Hibernate操作和保存方式
- Python 连接mysql
- telnet发电子邮件
- windows 安全模型简介
- 史上最全最强Charles截取手机https协议数据包教程(附上利用此技术制作最近微信比较火的头脑王者辅助外挂)!
- IDEA主类文件需要放置在SRC文件下,非包内
- Linux---基础命令(二)
- WinServerDFS
- OpenCV3.3.0 + CLion + CMake 配置(Mac巨细无敌版)
- NodeJS Web模块
- Pentaho data integration(kettle) 在Mac上启动不了