命运
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 2499 Accepted Submission(s): 893
Problem Description
穿过幽谷意味着离大魔王lemon已经无限接近了!
可谁能想到,yifenfei在斩杀了一些虾兵蟹将后,却再次面临命运大迷宫的考验,这是魔王lemon设下的又一个机关。要知道,不论何人,若在迷宫中被困1小时以上,则必死无疑!
可怜的yifenfei为了去救MM,义无返顾地跳进了迷宫。让我们一起帮帮执着的他吧!
命运大迷宫可以看成是一个两维的方格阵列,如下图所示:
yifenfei一开始在左上角,目的当然是到达右下角的大魔王所在地。迷宫的每一个格子都受到幸运女神眷恋或者痛苦魔王的诅咒,所以每个格子都对应一个值,走到那里便自动得到了对应的值。
现在规定yifenfei只能向右或者向下走,向下一次只能走一格。但是如果向右走,则每次可以走一格或者走到该行的列数是当前所在列数倍数的格子,即:如果当前格子是(x,y),下一步可以是(x+1,y),(x,y+1)或者(x,y*k) 其中k>1。
为了能够最大把握的消灭魔王lemon,yifenfei希望能够在这个命运大迷宫中得到最大的幸运值。
Input
输入数据首先是一个整数C,表示测试数据的组数。
每组测试数据的第一行是两个整数n,m,分别表示行数和列数(1<=n<=20,10<=m<=1000);
接着是n行数据,每行包含m个整数,表示n行m列的格子对应的幸运值K ( |k|<100 )。
Output
请对应每组测试数据输出一个整数,表示yifenfei可以得到的最大幸运值。
Sample Input
1
3 8
9 10 10 10 10 -10 10 10
10 -11 -1 0 2 11 10 -20
-11 -11 10 11 2 10 -10 -10
Sample Output
看到仙剑人物!不过还没玩完仙剑4。这题就是简单DP,就是数塔的变形版而已,基于数塔的题目,只要加些条件,状态转移方程很容易找到,这样就行了!
链接:http://acm.hdu.edu.cn/showproblem.php?pid=2571
代码:
#include <iostream>
#include <stdio.h>
#include <memory.h>
using namespace std;
int a[25][1005], sum[25][1005];
int main()
{
int i, j, k, t, n, m, MAX;
scanf("%d", &t);
while(t--)
{
scanf("%d %d", &n ,&m);
for(i = 0; i <= n; i++)
for(j = 0; j <= m; j++)
a[i][j] = -999;
for(i = 1; i <= n; i++)
for(j = 1; j <= m; j++)
scanf("%d", &a[i][j]);
for(i = 1; i <= n; i++)
{
for(j = 1; j <= m; j++)
{
MAX = -999;
for(k = 1; k < j; k++)
{
if(j%k == 0)
if(a[i][k] > MAX)
MAX = a[i][k];
}
if(i-1 >= 1 && j-1 >= 1)
a[i][j] += max( max(a[i-1][j], a[i][j-1]), MAX );
else if(i-1 >= 1)
a[i][j] += max( a[i-1][j], MAX );
else if(j - 1 >= 1)
a[i][j] += max( a[i][j-1], MAX );
}
}
printf("%d\n", a[n][m]);
}
return 0;
}
- 大小: 19 KB
- 大小: 59.6 KB
分享到:
相关推荐
算法-命运(HDU-2571)(包含源程序).rar
HDU的1250,主要是利用高精度加法,但是代码有点繁琐,效率不是很高
HDU1059的代码
杭电ACMhdu1163
hdu1001解题报告
hdu 1574 passed sorce
HDU的一题........HDU DP动态规
hdu acm 教案 搜索入门 hdu acm 教案 搜索入门
hdu2101AC代码
搜索 dfs 解题代码 hdu1241
hdu 5007 Post Robot 字符串枚举。 暴力一下就可以了。
hdu acm 教案 动态规划(1) hdu acm 教案 动态规划(1)
ACM HDU题目分类,我自己总结的大概只有十来个吧
hdu1290 解题报告 献给杭电五十周年校庆的礼物 (切西瓜问题,即平面分割空间)
HDU最全ac代码
hdu 1166线段树代码
hdu动态规划算法集锦
自己做的HDU ACM已经AC的题目
hdu题目分类
HDU图论题目分类