Time Limit: 1000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 106 Accepted Submission(s): 94
Problem Description
在講述DP算法的時候，一個經典的例子就是數塔問題，它是這樣描述的：
有如下所示的數塔，要求從頂層走到底層，若每一步隻能走到相鄰的結點，則經過的結點的數字之和最大是多少？
已經告訴你了，這是個DP的題目，你能AC嗎?
Input
輸入資料首先包括一個整數C,表示測試執行個體的個數，每個測試執行個體的第一行是一個整數N(1 <= N <= 100)，表示數塔的高度，接下來用N行數字表示數塔，其中第i行有個i個整數，且所有的整數均在區間[0,99]内。
Output
對于每個測試執行個體，輸出可能得到的最大和，每個執行個體的輸出占一行。
Sample Input
#include <iostream>
<b></b>
using namespace std<b>;</b><b></b>
int<b> main</b><b>()</b>
{<b></b>
int C<b>,</b>N<b>,</b>d<b>[</b>101<b>][</b>101<b>],</b>a<b>[</b>101<b>][</b>101<b>],</b>h<b>;</b>
cin<b>>></b>C<b>;</b><b></b>
while<b>(</b>C<b>--)</b>
{
cin<b>>></b>N<b>;</b>
h<b> =</b> N<b>;</b><b></b>
while<b>(</b>N<b>--)</b>
{<b></b>
for<b>(</b><b>int</b> i<b> =</b> 1<b>;</b> i<b><=(</b>h<b>-</b>N<b>);</b>i<b>++)</b>
{
cin<b>>></b>a<b>[</b>h<b>-</b>N<b>][</b>i<b>];</b>
}
}<b></b>
for<b>(</b><b>int</b> i<b> =</b> h<b>;</b> i<b>>=</b>1<b> ;</b>i<b>--)</b><b></b>
for<b>(</b><b>int</b> j<b> =</b> 1<b>;</b> j<b><=</b>i<b> ;</b>j<b>++)</b>
if<b>(</b>i<b>==</b>h<b>)</b>d<b>[</b>i<b>][</b>j<b>] =</b> a<b>[</b>i<b>][</b>j<b>];</b><b></b>
else
d<b>[</b>i<b>][</b>j<b>] =</b> a<b>[</b>i<b>][</b>j<b>] + (</b>d<b>[</b>i<b>+</b>1<b>][</b>j<b>]></b>d<b>[</b>i<b>+</b>1<b>][</b>j<b>+</b>1<b>]?</b>d<b>[</b>i<b>+</b>1<b>][</b>j<b>]:</b>d<b>[</b>i<b>+</b>1<b>][</b>j<b>+</b>1<b>]);</b>
}
cout<b><<</b>d<b>[</b>1<b>][</b>1<b>]<<</b>endl<b>;</b>
}<b></b>
return 0<b>;</b>
}
<b>本文轉自NewPanderKing51CTO部落格，原文連結：</b><b>http://www.cnblogs.com/newpanderking/archive/2011/08/03/2125819.html</b><b> ，如需轉載請自行聯系原作者</b>
![無人機--飛控科普[圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)