<h1 id="heading">题目</h1>
<blockquote>
<h2 id="description">Description</h2>
<blockquote>
在讲述DP算法的时候，一个经典的例子就是数塔问题，它是这样描述的：
有如下所示的数塔，要求从顶层走到底层，若每一步只能走到相邻的结点，则经过的结点的数字之和最大是多少？ 
<div class='image'><a href='http://acm.hdu.edu.cn/data/images/2084-1.jpg' target='_blank' rel='noopener noreferrer'><img src="http://acm.hdu.edu.cn/data/images/2084-1.jpg" /></a></div> 
已经告诉你了，这是个DP的题目，你能AC吗
 
</blockquote>
<h2 id="input">Input</h2>
<blockquote>
输入数据首先包括一个整数C,表示测试实例的个数，每个测试实例的第一行是一个整数N(1 &lt;= N &lt;= 100)，表示数塔的高度，接下来用N行数字表示数塔，其中第i行有个i个整数，且所有的整数均在区间[0,99]内。
</blockquote>
<h2 id="output">Output</h2>
<blockquote>
对于每个测试实例，输出可能得到的最大和，每个实例的输出占一行。
</blockquote>
<h2 id="sample-input">Sample Input</h2>
<blockquote>
1 
5 
7 
3 8 
8 1 0 
2 7 4 4 
4 5 2 6 5
</blockquote>
<h2 id="sample-output">Sample Output</h2>
<blockquote>
30
</blockquote>
</blockquote>
<h1 id="heading-1">题解</h1>
<a href="/post/AOJ/806.html">&gt;AOJ 806.算法期末考试B(动态规划)&lt;</a> 
原题
<h1 id="heading-2">代码</h1>
<pre style="background-color:#fff">/*
By:OhYee
Github:OhYee
HomePage:http://www.oyohyee.com
Email:oyohyee@oyohyee.com
Blog:http://www.cnblogs.com/ohyee/

かしこいかわいい？
エリーチカ！
要写出来Хорошо的代码哦~
*/

#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;
using namespace std;

//DEBUG MODE
#define debug 0

//循环
#define REP(n) for(int o=0;o&lt;n;o++)

const int maxn = 1000;

int Map[maxn][maxn];

bool Do() {
 int n;

 if(scanf(&#34;%d&#34;,&amp;n) == EOF)
 return false;

 memset(Map,0,sizeof(Map));

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

 for(int i = n - 1;i &gt; 0;i--)
 for(int j = 1;j &lt;= i;j++)
 Map[i][j] += max(Map[i + 1][j],Map[i + 1][j + 1]);
 printf(&#34;%d\n&#34;,Map[1][1]);
 return true;
}

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

HDU 2084.数塔