命运
Time Limit: 2000/1000 MS (Java/Others)Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 6270Accepted Submission(s): 2207
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
状态转移方程:
sum[i][j]=max{sum[i-1][j],sum[i][k]}+v[i][j];其中1<=k<=j-1,且k是j的因子
上面的要用二维数组。
其实完全可以优化为一维数组。这里用 opt[j] = max{ opt[j], {opt[k]} } + map[i][j] ; 其中1<=k<=j-1,且k是j的因子
另外,第一行要单独处理。
见代码:
#include <iostream>
#include <string.h>
#include <stdlib.h>
#include <fstream>
using namespace std;
int main() {
//ifstream cin("D:\\C++\\eclipse_work\\动态规划\\testcpp\\input.txt");
int k, m, n, temp;
cin >> k;
int opt[1002];
while (k--) {
memset(opt, 0, sizeof(opt));
cin >> m >> n;
cin >> opt[1]; //第一行第一列 没得选。
//遍历第一行. 由于第一行比较特殊,只能从左边到达,单独处理。
for (int j = 2; j <= n; j++) {
cin >> temp;
for (int k = 1; k <= j / 2; k++) {
if (j % k == 0) {
if (opt[j] ==0 || opt[j] < opt[k] + temp)
opt[j] = opt[k] + temp;
}
}
if ((j > 2 && opt[j] < opt[j - 1] + temp) || opt[j] ==0)
opt[j] = opt[j - 1] + temp;
}
//遍历后面几行。 两种可能 找到一个较大的即可
for (int i = 1; i < m; i++) {
for (int j = 1; j <= n; j++) {
cin >> temp;
int t = opt[j];
for (int k = 1; k <= j / 2; k++) {
if (j % k == 0) {
if ( opt[k] > t)
t = opt[k];
}
}
if (j > 2 && opt[j - 1] > t)
t = opt[j - 1] ;
opt[j] = t + temp;
}
}
cout << opt[n] << endl;
}
return 0;
}
分享到:
相关推荐
算法分析课件,以及习题,课件做的不错故分享
HOj DP 分类 HOj DP 分类 HOj DP 分类
hoj小部分题
HOJ题目备份
HOJ题目源码,Java语言描述。Online Judge:http://acm.hit.edu.cn
湖南大学HOJ部分题目的源代码,包括中国余数定理等内容的讲解
HOJ题目源码,Java语言描述。Online Judge:http://acm.hit.edu.cn
GRUB_CMDLINE_LINUX="cgroup_enable=memory swapaccount=1"然后运行以下命令: update-grub && reboot在Node.js项目中安装要求:纱线yarn add hoj-judger自己建造要求:CMake 3.4或更高版本,g ++ 9或更高版本./...
此资源为hoj的离线题库,有了这份资源可以在没有网络情况下刷题喽
动态规划入门,hdu上的动态规划入门题的结题报告。 hdu 1171,hdu 1059,hdu 2159,hdu 2191,hdu 3496
hoj 部分题目解题报告 c,cpp或java语言描述
基于SpringCloud与Vue前后端分离,分布式架构的在线测评平台OJ (An open source online judge system base on SpringBoot, Springcloud Alibaba and Vue.js !)
注意数据范围,所以要用long long
acm简单题集,适合初学者交流,400道简单题
c在线题库,希望大家下载 kjbjbk lnknn 你看了可能地方辅导书幅度不断说
杭州电子科技大学ACM-OJ系统的部分代码,对学习数据结构还有算法很有帮助
哈工大hoj1037,详细的源代码,附有注释,可以看懂。
杭州电子科技大学OJ 部分代码。新手必备~~
采用暴力的思想,搜索所有可能路径。 int matrix[7][7]; int n; void inttoseries(int i,int *s) //将数i化为n进制的n位数 {int k,j; for(k=0,j=i;k<n-1;++k) {s[k]=j%n;j/=n;} } int maxcolumn(int *s)//每列...
从零开始重写KOK1 1 BIN 让人物可在地图上使用鼠标跑动