题目：
Problem Description 穿过幽谷意味着离大魔王lemon已经无限接近了！可谁能想到，yifenfei在斩杀了一些虾兵蟹将后，却再次面临命运大迷宫的考验，这是魔王lemon设下的又一个机关。要知道，不论何人，若在迷宫中被困1小时以上，则必死无疑！
可怜的yifenfei为了去救MM，义无返顾地跳进了迷宫。让我们一起帮帮执着的他吧！
命运大迷宫可以看成是一个两维的方格阵列，如下图所示：
vce1xLTzxKfN9cv51Nq12KGjw9S5rLXEw7/Su7j2JiMyNjY4NDvX07a8yty1vdDS1MvFrsnxvuzBtbvy1d/NtL/gxKfN9bXE1+fW5KOsy/nS1MO/uPYmIzI2Njg0O9fTtry21NOm0ru49iYjMjA1NDA7o6zX37W9xMfA77Hj19S2r7XDtb3By7bU06a1xCYjMjA1NDA7oaM8YnI+Cs/W1Nq55raoeWlmZW5mZWnWu8Tcz/LT0rvy1d/P8s/C19+jrM/yz8LSu7TO1rvE3Nff0rsmIzI2Njg0O6GjtavKx8jnufvP8tPS19+jrNTyw7+0zr/J0tTX39K7JiMyNjY4NDu78tXf19+1vbjD0NC1xMHQyv3Kx7Wxx7DL+dTawdDK/bG2yv21xCYjMjY2ODQ719OjrLy0o7rI57n7tbHHsCYjMjY2ODQ719PKx6OoeCx5o6mjrM/C0ruyvb/J0tTKx6OoeCYjNDM7MSx5o6mjrCh4LHkmIzQzOzEpu/LV3yh4LHkqaykgxuTW0Gs+MaGjIDxicj4KzqrBy8TcubvX7rTzsNHO1bXEz/vD8MSnzfVsZW1vbqOseWlmZW5mZWnPo837xNy5u9Ta1eK49sP81Mu088PUuazW0LXDtb3X7rTztcTQ0tTLJiMyMDU0MDuhozxicj4KPGltZyBzcmM9"https://www.cppentry.com/upload_files/article/49/1_9yn3i__.jpg" alt="\">
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
52
Author yifenfei
Source ACM程序设计期末考试081230
这个题目是一个动态规划题...
主要是考虑在第1行第1 列的情况，所以要仔细判断。。。
这部分注意代码为：
if(i==1&&j==1) continue;
if(i==1&&j!=1) dp[i][j]=dp[i][j-1];
if(j==1&&i!=1) dp[i][j]=dp[i-1][j];
if(i!=1&&j!=1)
dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
代码为：
#include#include #include using namespace std; int map[25][1005],dp[25][1005]; int main() { int t,n,m,i,j,k; scanf("%d",&t); while(t--) { scanf("%d%d",&n,&m); for(i=1;i<=n;i++) for(j=1;j<=m;j++) scanf("%d",&map[i][j]); memset(dp,0,sizeof(dp)); dp[1][1]=map[1][1]; for(i=1;i<=n;i++) { for(j=1;j<=m;j++) { if(i==1&&j==1) continue; if(i==1&&j!=1) dp[i][j]=dp[i][j-1]; if(j==1&&i!=1) dp[i][j]=dp[i-1][j]; if(i!=1&&j!=1) dp[i][j]=max(dp[i-1][j],dp[i][j-1]); for(k=2;k<=m;k++) { if((double)j/k==j/k) dp[i][j]=max(dp[i][j],dp[i][j/k]); } dp[i][j]+=map[i][j]; } } printf("%d\n",dp[n][m]); } return 0; }