网站建设培训福州,wordpress文章添加返回目录,怎么用手机做钓鱼软件或者网站,20平办公室装修设计穿过幽谷意味着离大魔王lemon已经无限接近了#xff01; 可谁能想到#xff0c;yifenfei在斩杀了一些虾兵蟹将后#xff0c;却再次面临命运大迷宫的考验#xff0c;这是魔王lemon设下的又一个机关。要知道#xff0c;不论何人#xff0c;若在迷宫中被困1小时以上#xf…穿过幽谷意味着离大魔王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 题目说了半天其实就是个二维表格求最大值的dp 移动方法是向下走 或者向右走 向右走的话 就是走*1*2*3的位置或者向右移动一步 其实就是个dp 按照移动方法 不断更新结果矩阵的值 code: #includecstdio
#includecstring
#includeiostream
#includealgorithm
using namespace std;
int a[22][1010],b[22][1010];
int main()
{int t;cint;while(t--){int n,m;cinnm;for(int i1;in;i)//开始时 没有初始化 没考虑到有可能被更新成负值 for(int j1;jm;j)b[i][j]-110;for(int i1;in;i)for(int j1;jm;j)cina[i][j];for(int i1;in;i){ for(int j1;jm;j){if(j1i1)b[i][j]a[i][j];else if(j1i1)b[i][j]b[i-1][j]a[i][j];else if(i1j1)b[i][j]max(b[i][j],b[i][j-1])a[i][j];else if(i1j1){b[i][j]max(b[i][j],b[i][j-1]);b[i][j]max(b[i][j],b[i-1][j]);b[i][j]a[i][j];}for(int p1;p*jm;p)b[i][p*j]max(b[i][p*j],b[i][j]);}}
// for(int i1;in;i)
// {
// for(int j1;jm;j)
// coutb[i][j] ;
// coutendl;
// }printf(%d\n,b[n][m]);}return 0;
}
