hdu1978 How many ways--DP/记忆化搜索DFS
发布日期:2021-10-03 20:31:59 浏览次数:3 分类:技术文章

本文共 2071 字,大约阅读时间需要 6 分钟。

原题链接:

一:原题内容

Problem Description
这是一个简单的生存游戏,你控制一个机器人从一个棋盘的起始点(1,1)走到棋盘的终点(n,m)。游戏的规则描述如下:
1.机器人一开始在棋盘的起始点并有起始点所标有的能量。
2.机器人只能向右或者向下走,并且每走一步消耗一单位能量。
3.机器人不能在原地停留。
4.当机器人选择了一条可行路径后,当他走到这条路径的终点时,他将只有终点所标记的能量。
如上图,机器人一开始在(1,1)点,并拥有4单位能量,蓝色方块表示他所能到达的点,如果他在这次路径选择中选择的终点是(2,4)
点,当他到达(2,4)点时将拥有1单位的能量,并开始下一次路径选择,直到到达(6,6)点。
我们的问题是机器人有多少种方式从起点走到终点。这可能是一个很大的数,输出的结果对10000取模。
 
Input
第一行输入一个整数T,表示数据的组数。
对于每一组数据第一行输入两个整数n,m(1 <= n,m <= 100)。表示棋盘的大小。接下来输入n行,每行m个整数e(0 <= e < 20)。
 
Output
对于每一组数据输出方式总数对10000取模的结果.
 
Sample Input
16 64 5 6 6 4 32 2 3 1 7 21 1 4 6 2 75 8 4 3 9 57 6 6 2 1 53 1 1 3 7 2
 
Sample Output
3948

二:分析理解

这题题意有点问题,见杭电讨论区:http://acm.hdu.edu.cn/discuss/problem/list.php?problemid=1978

两个解法。

解法一:是纯DP,dp[i][j]代表从起点到ij的方式个数。

解法二:是DP+DFS,dp[i][j]代表ij到终点的方式个数。

三:AC代码

解法一:DP

#include
#include
#include
using namespace std;int dp[110][110];int main(){ int T; int x; int n, m; scanf("%d", &T); while (T--) { scanf("%d%d", &n, &m); memset(dp, 0, sizeof(dp)); dp[0][0] = 1; for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { scanf("%d", &x); for (int k = 0; k <= x; k++) { for (int v = 0; v <= x - k; v++) { if (k == 0 && v == 0)// continue; if (i + k < n&&j + v < m) dp[i + k][j + v] = (dp[i][j] + dp[i + k][j + v]) % 10000; } } } } printf("%d\n", dp[n-1][m-1]); } return 0;}

解法二:DP+DFS

#include
#include
#include
using namespace std;int dp[110][110];int map[110][110];int n, m;int DFS(int i, int j, int w){ if (dp[i][j] > 0) return dp[i][j]; for (int k = 0; k <= w; k++) { for (int v = 0; v <= w - k; v++) { if (k == 0 && v == 0) continue; if (i + k < n&&j + v < m) dp[i][j] = (dp[i][j] + DFS(i + k, j + v, map[i + k][j + v])) % 10000; } } return dp[i][j];}int main(){ int T; scanf("%d", &T); while (T--) { scanf("%d%d", &n, &m); memset(dp, 0, sizeof(dp)); dp[n-1][m-1] = 1; for (int i = 0; i < n; i++) for (int j = 0; j < m; j++) scanf("%d", &map[i][j]); printf("%d\n", DFS(0, 0, map[0][0])); } return 0;}

转载地址:https://blog.csdn.net/LaoJiu_/article/details/50973251 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!

上一篇:hdu1024 Max Sum Plus Plus--DP
下一篇:真是尿了!掉进了一个“盲僧”都能绕过的坑

发表评论

最新留言

表示我来过!
[***.240.166.169]2024年03月11日 01时07分14秒

关于作者

    喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!

推荐文章

mysql中sql语句结构_MySQL中使用sql语句获得表结构 2019-04-21
如何增加mysql主键约束_mysql修改表时怎么添加主键约束? 2019-04-21
java选择路径窗口_Java实现选择电脑路径的方法 2019-04-21
java 图像渐变_Java基础之在窗口中绘图——渐变填充(GradientApplet 1) 2019-04-21
冒泡排序面向对象java_所谓的面向对象实现的冒泡排序 2019-04-21
proto 客户端 JAVA_Kubernetes官方java客户端之五:proto基本操作 2019-04-21
java编写roguelike_RogueLike地牢生成算法Unity实现 2019-04-21
java ajax 修改数据库数据库数据库_AJAX 自学练习 无刷新提交并修改数据库数据并显... 2019-04-21
java并发编程指南博客_Java并发编程-synchronized指南 2019-04-21
java怎么中断阻塞状态_java并发编程()阻塞方法与中断方法 2019-04-21
java zlib 位运算_位运算入门:找出一个二进制数的最右端的第一个1;计算一个二进制数中1的个数;找出数组中唯一一个出现次数为奇数的数;找出数组中唯二两个出现次数为奇数的数... 2019-04-21
java lua热更新_lua热更新学习 2019-04-21
script执行php文件_php命令行(cli)下执行PHP脚本文件的相对路径的问题解决方法... 2019-04-21
apache 2.4 php5.4_apache2.4+php5.4+my sql 5.6,网站经常无故不能访问 2019-04-21
php apc.dll下载,PHP之APC缓存详细介绍 apc模块安装 2019-04-21
html贝塞尔曲线在线,贝塞尔曲线的一些事情_html/css_WEB-ITnose 2019-04-21
java blockingqueue源码_Java并发队列BlockingQueue实现之ArrayBlockingQueue源码分析 2019-04-21
Java前台显示近20天的东西_第十次课:前台首页设计及显示商品信息 2019-04-21
java开发web网站的路由设计_理解Web路由(浅谈前后端路由与前后端渲染) 2019-04-21
excel如何把顺序倒过来_在excel中怎么使文字颠倒顺序反过来显示呢? 2019-04-21