# 题目

## Description

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

52

# 题解

• (x-1,y)
• (x,y-1)
• (x,k) 其中 ky 的因数

dp[i][j] = max{ dp[i-1][j] , dp[i][j-1] , dp[i][k] } + Map[i][j]
( ky 的因数, Map[i][j](i,j) 的权值)

3 5
-1 -1 -1 -1 -1
-1 -1 -1 -1 -1
-1 -1 -1 -1 -1

for(int i = 1;i <= n;i++)
for(int j = 1;j <= m;j++) {
if(i == 1)
if(j == 1)
dp[i][j] = Map[i][j];
else
dp[i][j] = dp[1][1] + Map[i][j];
else
dp[i][j] = dp[i - 1][j] + Map[i][j];
for(int k = 1;k < j;k++)
if(j % k == 0 || k == j - 1)
dp[i][j] = max(dp[i][j],dp[i][k] + Map[i][j]);
}

# 代码

/*
By:OhYee
Github:OhYee
Blog:http://www.oyohyee.com/
Email:oyohyee@oyohyee.com

かしこいかわいい？
エリーチカ！

*/
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <string>
#include <iostream>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <functional>
using namespace std;

const int maxn = 25;
const int maxm = 1005;

int Map[maxn][maxm];
int dp[maxn][maxm];

void  Do() {
int n,m;
scanf("%d%d",&n,&m);

for(int i = 1;i <= n;i++)
for(int j = 1;j <= m;j++)
scanf("%d",&Map[i][j]);

for(int i = 1;i <= n;i++)
for(int j = 1;j <= m;j++) {
if(i == 1)
if(j == 1)
dp[i][j] = Map[i][j];
else
dp[i][j] = dp[1][1] + Map[i][j];
else
dp[i][j] = dp[i - 1][j] + Map[i][j];
for(int k = 1;k < j;k++)
if(j % k == 0 || k == j - 1)
dp[i][j] = max(dp[i][j],dp[i][k] + Map[i][j]);
}

printf("%d\n",dp[n][m]);
}

int main() {
int T;
scanf("%d",&T);
while(T--)
Do();
return 0;
}