php视频网站怎么做,如何设置网站,查询域名注册信息,互联网营销的十五种方式题干#xff1a;
穿过幽谷意味着离大魔王lemon已经无限接近了#xff01; 可谁能想到#xff0c;yifenfei在斩杀了一些虾兵蟹将后#xff0c;却再次面临命运大迷宫的考验#xff0c;这是魔王lemon设下的又一个机关。要知道#xff0c;不论何人#xff0c;若在迷宫中被…题干
穿过幽谷意味着离大魔王lemon已经无限接近了 可谁能想到yifenfei在斩杀了一些虾兵蟹将后却再次面临命运大迷宫的考验这是魔王lemon设下的又一个机关。要知道不论何人若在迷宫中被困1小时以上则必死无疑 可怜的yifenfei为了去救MM义无返顾地跳进了迷宫。让我们一起帮帮执着的他吧 命运大迷宫可以看成是一个两维的方格阵列如下图所示 yifenfei一开始在左上角目的当然是到达右下角的大魔王所在地。迷宫的每一个格子都受到幸运女神眷恋或者痛苦魔王的诅咒所以每个格子都对应一个值走到那里便自动得到了对应的值。 现在规定yifenfei只能向右或者向下走向下一次只能走一格。但是如果向右走则每次可以走一格或者走到该行的列数是当前所在列数倍数的格子即如果当前格子是x,y下一步可以是x1,y(x,y1)或者(x,y*k) 其中k1。 为了能够最大把握的消灭魔王lemonyifenfei希望能够在这个命运大迷宫中得到最大的幸运值。
Input
输入数据首先是一个整数C表示测试数据的组数。 每组测试数据的第一行是两个整数n,m分别表示行数和列数(1n20,10m1000) 接着是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
52
题目大意 中文题不解释啦~
解题报告 记忆化搜索。还是有小问题需要注意一下
AC代码
#includebits/stdc.husing namespace std;
const int INF 0x3f3f3f3f;
int n,m;
int maze[25][1005];
int dp[25][1005];
int dfs(int x,int y) {if(x n y m) return maze[n][m];if(dp[x][y] ! -INF) return dp[x][y];//忘了加负号 int maxx -INF;if(x1 n) maxx max(maxx,dfs(x1,y) maze[x][y]);if(y1m) maxx max(maxx,dfs(x,y1) maze[x][y]);for(int i 2*y; im; iy) {//别想当然写imaxx max(dfs(x,i) maze[x][y],maxx);}return dp[x][y] maxx;}int main()
{int t;cint;while(t--) {scanf(%d%d,n,m);for(int i 1; in; i) {for(int j 1 ; jm; j) {scanf(%d,maze[i][j]);dp[i][j] -INF;}}dp[n][m] maze[n][m];printf(%d\n,dfs(1,1));
// for(int i 1; in; i) {
// for(int j 1; jm; j) {
// printf(%d ,dp[i][j]);
// }
// printf(\n);
// }}return 0 ;}
