【HDU 2571 命运 +dp】
发布日期:2021-11-04 12:59:40
浏览次数:5
分类:技术文章
本文共 1681 字,大约阅读时间需要 5 分钟。
命运
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 -10Sample Output
52Author
yifenfei裸 dp 题 :
#include#include using namespace std;int dp[21][1011];int main(){ int T,N,M,i,j,kl,ans; scanf("%d",&T); while(T--) { scanf("%d%d",&N,&M); for(i = 1 ; i <= N ; i++) for(j = 1 ; j<= M ; j++) scanf("%d",&dp[i][j]); for(i = 1 ; i <= N ; i++) dp[i][0] = -110; for(j = 1 ; j <= M ; j++) dp[0][j] = -110; dp[1][0] = dp[0][1] = 0; for(i = 1 ; i <= N ; i++) for(j = 1; j <= M ; j++) { ans = max(dp[i - 1][j] , dp[i][j - 1]); for(kl = 1 ; kl <= j/2 ; kl++) { if(j % kl ==0) ans = max(ans,dp[i][kl]); } dp[i][j] += ans; } printf("%d\n",dp[N][M]); } return 0;}
转载地址:https://blog.csdn.net/WYK1823376647/article/details/52618162 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!
发表评论
最新留言
不错!
[***.144.177.141]2024年04月08日 20时05分18秒
关于作者
喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!
推荐文章
unity mesh合并
2019-04-27
谈谈类之间的关联关系与依赖关系
2019-04-27
unity5.x assetbundle打包和加载
2019-04-27
C#用正则表达式去匹配被双引号包起来的中文
2019-04-27
lua table排序
2019-04-27
Unity发布的ios包在iphone上声音是从听筒里出来的问题
2019-04-27
UIScrollView复用节点示例
2019-04-27
Unity 5 AudioMixer
2019-04-27
Unity 代码混淆: CodeGuard的使用
2019-04-27
UGUI 列表循环使用
2019-04-27
使用命令行运行unity并执行某个静态函数(运用于命令行打包和批量打包)
2019-04-27
web.py框架
2019-04-27
web.py学习笔记
2019-04-27
python的代码缩进
2019-04-27
A* Pathfinding Project (Unity A*寻路插件) 使用教程
2019-04-27
bash学习笔记
2019-04-27
sqlite学习
2019-04-27
手把手教你实现Unity与Android的交互
2019-04-27
手把手教你使用Unity的Behavior Designer
2019-04-27