HDU 1978 How many ways(动态规划)
2024-09-22 17:08:18
How many ways
http://acm.hdu.edu.cn/showproblem.php?pid=1978
Problem Description
这是一个简单的生存游戏,你控制一个机器人从一个棋盘的起始点(1,1)走到棋盘的终点(n,m)。游戏的规则描述如下:
1.机器人一开始在棋盘的起始点并有起始点所标有的能量。
2.机器人只能向右或者向下走,并且每走一步消耗一单位能量。
3.机器人不能在原地停留。
4.当机器人选择了一条可行路径后,当他走到这条路径的终点时,他将只有终点所标记的能量。
如上图,机器人一开始在(1,1)点,并拥有4单位能量,蓝色方块表示他所能到达的点,如果他在这次路径选择中选择的终点是(2,4)
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)。
对于每一组数据第一行输入两个整数n,m(1 <= n,m <= 100)。表示棋盘的大小。接下来输入n行,每行m个整数e(0 <= e < 20)。
Output
对于每一组数据输出方式总数对10000取模的结果.
Sample Input
1
6 6
4 5 6 6 4 3
2 2 3 1 7 2
1 1 4 6 2 7
5 8 4 3 9 5
7 6 6 2 1 5
3 1 1 3 7 2
Sample Output
3948
题目没说太清楚,有一点就是可以在能量没耗尽之前可以停!
解题代码:
#include <stdio.h>
#include <iostream>
#include <string.h>
using namespace std; const int max_n = ; int dp[max_n][max_n]; int main ()
{
int T, n, m;
scanf ("%d", &T);
while (T--)
{
scanf ("%d%d", &n, &m);
memset(dp, , sizeof (dp));
dp[][] = ;
for (int i = ; i < n; i ++)
{
for (int j = ; j < m; j ++)
{
int val;
scanf ("%d", &val);
for (int k = ; k <= val; k ++)//不能超过能量范围
{
for (int l = ; l + k <= val; l ++)
{
if (l == k && k == )
continue;
dp[i+k][j+l] = (dp[i][j] + dp[i+k][j+l])%;//新增的路径数加上本来的路径数
}
}
}
}
printf ("%d\n", dp[n-][m-]);
}
return ;
}
G++
最新文章
- MVVM TextBox的键盘事件
- ASP.NET MVC Model绑定(四)
- FZU 1914 单调队列
- CSS常用属性
- mysql开启慢查询
- 如何让Targetprocess 中 webhook 推送comment 到指定的项目
- 单元测试篇----cppUnit的安装与使用
- 30+简约时尚的Macbook贴花
- 【转】 ASP.NET网站路径中~(波浪线)解释
- 第五篇、Uber用视频播放做启动动画
- 发现SQL Server惊天大秘密!!
- [转]Pig与Hive 概念性区别
- 大牛教你用3行HTML代码卡死一台机器
- TDD 之 Dojo coding
- JS中的递归
- SpringBatch的核心组件JobLauncher和JobRepository
- 【Unity Shaders】Using Textures for Effects——通过修改UV坐标来滚动textures
- awk小例子_2_数值统计脚本
- 剖析项目多个logback配置(上)
- [sklearn] 官方例程-Imputing missing values before building an estimator 随机填充缺失值