这篇博客是从旧博客 WordPress 迁移过来,内容可能存在转换异常。
题目地址:
http://acm.hdu.edu.cn/showproblem.php?pid=2084
自底而上。一步步求最优。
// Author: Tanky Woo
// HDOJ 2084
// Accepted 2084 15MS 220K 567B C++
// 状态转移方程:
// Tower[i][j] = max(Tower[i+1][j], Tower[i+1][j+1]);
#include
using namespace std;
int nCases;
int nHeight;
int Tower[101][101];
int _max(int a, int b)
{
return a>b? a: b;
}
int main()
{
freopen("input.txt", "r", stdin);
scanf("%d", &nCases;);
while(nCases--)
{
scanf("%d", &nHeight;);
for(int i=0; i=0; --i)
for(int j=0; j<=i; ++j)
Tower[i][j] += _max(Tower[i+1][j], Tower[i+1][j+1]);
printf("%d\n", Tower[0][0]);
}
return 0;
}