命运
http://acm.hdu.edu.cn/showproblem.php?pid=2571
可谁能想到,yifenfei在斩杀了一些虾兵蟹将后,却再次面临命运大迷宫的考验,这是魔王lemon设下的又一个机关。要知道,不论何人,若在迷宫中被困1小时以上,则必死无疑!
可怜的yifenfei为了去救MM,义无返顾地跳进了迷宫。让我们一起帮帮执着的他吧!
命运大迷宫可以看成是一个两维的方格阵列,如下图所示:
yifenfei一开始在左上角,目的当然是到达右下角的大魔王所在地。迷宫的每一个格子都受到幸运女神眷恋或者痛苦魔王的诅咒,所以每个格子都对应一个值,走到那里便自动得到了对应的值。
现在规定yifenfei只能向右或者向下走,向下一次只能走一格。但是如果向右走,则每次可以走一格或者走到该行的列数是当前所在列数倍数的格子,即:如果当前格子是(x,y),下一步可以是(x+1,y),(x,y+1)或者(x,y*k) 其中k>1。
为了能够最大把握的消灭魔王lemon,yifenfei希望能够在这个命运大迷宫中得到最大的幸运值。
每组测试数据的第一行是两个整数n,m,分别表示行数和列数(1<=n<=20,10<=m<=1000);
接着是n行数据,每行包含m个整数,表示n行m列的格子对应的幸运值K ( |k|<100 )。
10 -11 -1 0 2 11 10 -20
-11 -11 10 11 2 10 -10 -10
解题思路:动态方程很容易推出,关键是要注意边界的处理!
解题代码:
#include <stdio.h>
#include <string.h> const int max_n = ;
const int max_m = ;
int map[max_n][max_m];
int dp[max_n][max_m]; int max(int a, int b, int c = -0x3fffffff)
{
if (a < b)
a = b;
if (a < c)
a = c;
return a;
} int main()
{
int n, m, T;
scanf ("%d", &T);
while (T--)
{
for (int i = ; i < max_n; i ++)
for (int j = ; j < max_m; j ++)
dp[i][j] = -0x3fffffff;
scanf ("%d%d", &n, &m);
for (int i = ; i <= n; i ++)
{
for (int j = ; j <= m; j ++)
{
scanf ("%d", &map[i][j]);
}
}
dp[][] = map[][];
for (int i = ; i <= n; i ++)
{
int max_i = -0x3fffffff;
for (int j = ; j <= m; j ++)
{
if(i==&&j==) continue;
if( i > )
dp[i][j] = max(dp[i][j], dp[i-][j] + map[i][j]);
if( j > )
dp[i][j] = max(dp[i][j], dp[i][j-] + map[i][j]);
int k = j - ;
while( k > )
{
if (j%k == )
dp[i][j] = max(dp[i][j], dp[i][k] + map[i][j]);
k--;
}
}
}
printf ("%d\n", dp[n][m]);
}
return ;
}
HDU 2571 命运 动态规划的更多相关文章
-
HDU 2571 命运 (DP)
命运 Time Limit:1000MS Memory Limit:32768KB 64bit IO Format:%I64d & %I64u Submit Status Pr ...
-
命运(HDU 2571 简单动态规划)
命运 Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)Total Submissi ...
-
hdu 2571 (命运) 那个配图女神
http://acm.hdu.edu.cn/showproblem.php?pid=2571 枚举每一个点,找出按照题目要求的这个点的上一点的最大值,合并到当前点,注意只取前面的一种情况 #inclu ...
-
HDU 2571 命运
命运 Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)Total Submissi ...
-
hdu 2571 命运(dp)
Problem Description 穿过幽谷意味着离大魔王lemon已经无限接近了! 可谁能想到,yifenfei在斩杀了一些虾兵蟹将后,却再次面临命运大迷宫的考验,这是魔王lemon设下的又一个 ...
-
HDU 2571 命运 (简单DP)
命运 Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)Total Submissi ...
-
HDU - 2571 命运 DP倍数跳跃处理
命运 穿过幽谷意味着离大魔王lemon已经无限接近了! 可谁能想到,yifenfei在斩杀了一些虾兵蟹将后,却再次面临命运大迷宫的考验,这是魔王lemon设下的又一个机关.要知道,不论何人,若在迷宫中 ...
-
hdu 2571 命运(递推,请小心)
题目 //不能广搜,会超内存//可以用dp思想模拟//map 后来保存的是 保存由前面推来的最大的幸运总值的点//下标从1开始,不然倍数会有问题 //AC 代码: AC代码 //不能广搜,会超内存 / ...
-
HDU 2571 命运(简单dp)
传送门 真是刷越多题,越容易满足.算是一道很简单的DP了.终于可以自己写出来了. 二维矩阵每个点都有一个幸运值,要求从左上走到右下最多能积累多少幸运值. 重点就是左上右下必须都踩到. dp[i][j] ...
随机推荐
-
Spring集成JUnit测试
1.程序中有Junit环境2.导入一个jar包.spring与junit整合jar包 spring-test-3.2.0.RELEASE.jar3.测试代码 @RunWith(SpringJUnit4 ...
-
mariadb DML语句及用户授权
DML(Data Manipulation Language):INSERT, DELETE, UPDATE, SELECT INSERT [INTO] tbl_name [(col1,...) ...
-
Drozer安装
(1)JDK安装 http://www.cnblogs.com/linbc/p/4319509.html http://blog.csdn.net/qq_31988895/article/detail ...
-
git删除中文文件
git中出现如下代码时,是因为文件中包含中文.而且我们也无法用 git rm name 命令来删除该文件. deleted: "chrome_plugin/source_file/iHub\ ...
-
简单易学的机器学习算法——EM算法
简单易学的机器学习算法——EM算法 一.机器学习中的参数估计问题 在前面的博文中,如“简单易学的机器学习算法——Logistic回归”中,采用了极大似然函数对其模型中的参数进行估计,简单来讲即对于一系 ...
-
.NetCore~Json代替了Xml
回到目录 在进行.netCore时代后,最大的变化就是对Json的使用更加主动,基本代替了之前的XML,像一些用户配置,系统配置,包包配置等都是基于json的,而web.config这个文件基本变成一 ...
-
读书笔记-你不知道的JS上-this
关于this 与静态词法作用域不用,this的指向动态绑定,在函数执行期间才能确定.感觉有点像C++的多态? var a = 1; var obj = { a: 2, fn: function() { ...
-
Android Service组件在新进程绑定(bindService)过程
1.首先看两个样例 (1)进程内 Client端 public class CounterService extends Service implements ICounterService { .. ...
-
iview 3.x InputNumber数字框bug
iview 3.X 版本中InputNumber 数字框组件存在bug,把最小值设置为0.2时,数组框禁止点击,其他数字都是正常.
-
关于Flume中Chanel.Selector.header解释
flume内置的ChannelSelector有两种,分别是Replicating和Multiplexing. Replicating类型的ChannelSelector会针对每一个Event,拷贝到 ...