Blog·Tanky WooABOUTRSS

HDOJ 2084 数塔

28 Jul 2010
这篇博客是从旧博客 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;
}