【一本通基础DP基础模型】摘花生
2024-10-20 20:33:10
题面
题目描述
Hello Kitty想摘点花生送给她喜欢的米老鼠。她来到一片有网格状道路的矩形花生地(如下图),从西北角进去,东南角出来。地里每个道路的交叉点上都有种着一株花生苗,上面有若干颗花生,经过一株花生苗就能摘走该它上面所有的花生。Hello Kitty只能向东或向南走,不能向西或向北走。问Hello Kitty最多能够摘到多少颗花生。
输入格式
第一行是一个整数T,代表一共有多少组数据。1≤T≤100
接下来是T组数据。
每组数据的第一行是两个整数,分别代表花生苗的行数R和列数 C(1≤R,C≤100)
每组数据的接下来R行数据,从北向南依次描述每行花生苗的情况。每行数据有C个整数,按从西向东的顺序描述了该行每株花生苗上的花生数目M(0≤M≤1000)。
输出格式
对每组输入数据,输出一行,内容为Hello Kitty能摘到得最多的花生颗数。
样例
2
2 2
1 1
3 4
2 3
2 3 4
1 6 5
8
16
思路
考虑使用 DP
,用集合 dp[i][j]
表示从起点(即 dp[1][1]
)到点 (i,j)
的所有路线,其中 dp[i][j]
的数值表示这个集合的每条路线中摘到花生数的最大值。那么 dp[r][c]
即为最终答案。下面推导状态转移方程。
- 初始化:所有点的值均为原地图值(边界为0)
具体实现方式:#include<bits/stdc++.h>
using namespace std;
int dp[105][105];//全局变量即可初始化为0
int main()
{
int T;
cin>>T;//读入T组数据
while(T--)
{
int r,c;
scanf("%d%d",&r,&c);//每组数据读入地图长宽
for(register int i(1);i<=r;++i)//register, i(1), ++i 均为卡常优化
for(register int j(1);j<=c;++j)
scanf("%d",&dp[i][j]);//读入地图
...
}
}
- 每次到一个点摘花生的最大值=前面到这个点的最大值+这个点
那么,前面到这个点的最大值怎么求呢?
由于只能朝右或下走,所以前面到这个点只能从左侧或上边来,所以说,只要将左侧dp[i][j-1]
与上边dp[i-1][j]
取max
即可。
具体实现方法:for(register int i(1);i<=r;++i)
for(register int j(1);j<=c;++j)
dp[i][j]=max(dp[i-1][j],dp[i][j-1])+dp[i][j];//按照前面推导的思路进行dp
- 输出
dp[r][c]
即可。
具体实现方法:printf("%d\n",dp[r][c]);//读出最后一个点能摘到的最多花生
最后附上完整代码
#include<bits/stdc++.h>
using namespace std;
int dp[105][105];//全局变量即可初始化为0
int main()
{
int T;
cin>>T;//读入T组数据
while(T--)
{
int r,c;
scanf("%d%d",&r,&c);//每组数据读入地图长宽
for(register int i(1);i<=r;++i)//register, i(1), ++i 均为卡常优化
for(register int j(1);j<=c;++j)
scanf("%d",&dp[i][j]);//读入地图
for(register int i(1);i<=r;++i)
for(register int j(1);j<=c;++j)
dp[i][j]=max(dp[i-1][j],dp[i][j-1])+dp[i][j];//按照前面推导的思路进行dp
printf("%d\n",dp[r][c]);//读出最后一个点能摘到的最多花生
}
}
最新文章
- H5 canvas的 width、height 与style中宽高的区别
- (转)sqlplus中文显示乱码的问题
- CentOS 6.4下PXE+Kickstart无人值守安装操作系统
- Unity3D获取Andorid设备返回键,主页键等功能
- C# Stream 和 byte[] 之间的转换(文件流的应用)
- Base64编码简介
- Sping mvc 环境下使用kaptcha 生成验证码
- 第二次正式java web开发项目的总结(回收站恢复)
- 《A Tour of PostgreSQL Internals》学习笔记——进程间通信
- Win7下通过easyBCD引导安装Ubuntu14.04
- Python的ASCII, GB2312, Unicode , UTF-8 相互转换
- 【Unity优化】Unity优化技巧进阶开篇
- 从";按层次输出二叉树";到";求解二叉树深度";的总结
- DDGScreenShot--iOS 图片处理--多图片拼接 (swift)
- Java中的AES加解密
- Linux常用基本命令:三剑客命令之-awk模式用法(2)
- 以用户注册功能模块为例浅谈MVC架构下的JavaWeb开发流程
- python的日志模块logging和syslog
- Docker搭建 MySQL 主从复制
- Java之集合(十五)Set综述
热门文章
- UART串口及Linux实现
- Django学习——ajax发送其他请求、上传文件(ajax和form两种方式)、ajax上传json格式、 Django内置序列化(了解)、分页器的使用
- Web安全学习笔记 SQL注入上
- ThinkPHP V6.0.12在php8.1下验证码出现问题
- linux篇-centos7安装DHCP服务器
- C# 通关手册(持续更新......)
- 【单片机】CH32V103C8T6定时器3程序实验
- python并发编程之线程/协程
- 大白话讲Java的锁
- 「ARC 139F」Many Xor Optimization Problems【线性做法,踩标】