<h1 id="heading">题目</h1>
<blockquote>
<h2 id="description">Description</h2>
<blockquote>
穿过幽谷意味着离大魔王lemon已经无限接近了！ 
可谁能想到，yifenfei在斩杀了一些虾兵蟹将后，却再次面临命运大迷宫的考验，这是魔王lemon设下的又一个机关。要知道，不论何人，若在迷宫中被困1小时以上，则必死无疑！ 
可怜的yifenfei为了去救MM，义无返顾地跳进了迷宫。让我们一起帮帮执着的他吧！ 
命运大迷宫可以看成是一个两维的方格阵列，如下图所示：
<div class='image'><a href='http://acm.hdu.edu.cn/data/images/C164-1005-1.jpg' target='_blank' rel='noopener noreferrer'><img src="http://acm.hdu.edu.cn/data/images/C164-1005-1.jpg" /></a></div>
yifenfei一开始在左上角，目的当然是到达右下角的大魔王所在地。迷宫的每一个格子都受到幸运女神眷恋或者痛苦魔王的诅咒，所以每个格子都对应一个值，走到那里便自动得到了对应的值。 
现在规定yifenfei只能向右或者向下走，向下一次只能走一格。但是如果向右走，则每次可以走一格或者走到该行的列数是当前所在列数倍数的格子，即：如果当前格子是（x,y），下一步可以是（x+1,y），(x,y+1)或者(x,y*k) 其中k&gt;1。 
为了能够最大把握的消灭魔王lemon，yifenfei希望能够在这个命运大迷宫中得到最大的幸运值。
 
</blockquote>
<h2 id="input">Input</h2>
<blockquote>
输入数据首先是一个整数C，表示测试数据的组数。 
每组测试数据的第一行是两个整数n,m，分别表示行数和列数(1&lt;=n&lt;=20,10&lt;=m&lt;=1000)； 
接着是n行数据，每行包含m个整数，表示n行m列的格子对应的幸运值K ( |k|&lt;100 )。
</blockquote>
<h2 id="output">Output</h2>
<blockquote>
请对应每组测试数据输出一个整数，表示yifenfei可以得到的最大幸运值。
</blockquote>
<h2 id="sample-input">Sample Input</h2>
<blockquote>
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
</blockquote>
<h2 id="sample-output">Sample Output</h2>
<blockquote>
52
</blockquote>
</blockquote>
<h1 id="heading-1">题解</h1>
动态规划问题 
对于 <code>(x,y)</code> 可以由以下点到达
<ul>
<li><code>(x-1,y)</code></li>
<li><code>(x,y-1)</code></li>
<li><code>(x,k)</code> 其中 <code>k</code> 是 <code>y</code> 的因数</li>
</ul>
那么,有 
<code>dp[i][j] = max{ dp[i-1][j] , dp[i][j-1] , dp[i][k] } + Map[i][j]</code> 
( <code>k</code> 是 <code>y</code> 的因数, <code>Map[i][j]</code> 是 <code>(i,j)</code> 的权值)
对于 <code>i == 1</code> 的情况需要特别处理
<blockquote>
3 5 
-1 -1 -1 -1 -1 
-1 -1 -1 -1 -1 
-1 -1 -1 -1 -1
</blockquote>
应该输出 <code>-4</code> 而不是 <code>-3</code>
<pre style="background-color:#fff"> for(int i = 1;i &lt;= n;i++)
 for(int j = 1;j &lt;= 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 &lt; j;k++)
 if(j % k == 0 || k == j - 1)
 dp[i][j] = max(dp[i][j],dp[i][k] + Map[i][j]);
 }
</pre><h1 id="heading-2">代码</h1>
<pre style="background-color:#fff">/*
By:OhYee
Github:OhYee
Blog:http://www.oyohyee.com/
Email:oyohyee@oyohyee.com

かしこいかわいい？
エリーチカ！
要写出来Хорошо的代码哦~
*/
#include &lt;cstdio&gt;
#include &lt;algorithm&gt;
#include &lt;cstring&gt;
#include &lt;cmath&gt;
#include &lt;string&gt;
#include &lt;iostream&gt;
#include &lt;vector&gt;
#include &lt;list&gt;
#include &lt;queue&gt;
#include &lt;stack&gt;
#include &lt;map&gt;
#include &lt;set&gt;
#include &lt;functional&gt;
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(&#34;%d%d&#34;,&amp;n,&amp;m);

 for(int i = 1;i &lt;= n;i++)
 for(int j = 1;j &lt;= m;j++)
 scanf(&#34;%d&#34;,&amp;Map[i][j]);

 for(int i = 1;i &lt;= n;i++)
 for(int j = 1;j &lt;= 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 &lt; j;k++)
 if(j % k == 0 || k == j - 1)
 dp[i][j] = max(dp[i][j],dp[i][k] + Map[i][j]);
 }

 printf(&#34;%d\n&#34;,dp[n][m]);
}

int main() {
 int T;
 scanf(&#34;%d&#34;,&amp;T);
 while(T--)
 Do();
 return 0;
}
</pre>

HDU 2571.命运