杭电 hdu 1176 免费馅饼

这是数塔的变形题刚开始不会做，后来找到基础的数塔题，练习之后，就OK了，但还是遇到了许多问题。建议理解不了的同学，先去做几题数塔的基础题。如

http://acm.hdu.edu.cn/showproblem.php?pid=2084

这里应该注意几点：

1. 制成数塔表。

2. 自下往上计算。

3. 计算到最顶层，也就是第 1 秒，最终的结果应该是中间位置的那个值。也就是代码中的：maxSum = dp[0][6];

上代码：

/* THE ROGRAM IS MADE BY PYY */
/*----------------------------------------------------------------------------//

        URL   :http://acm.hdu.edu.cn/showproblem.php?pid=1176
        Name  :1176 免费馅饼

        Date  : 2011/4/9 Thursday
        Times Stage(s) : more than 3 hours

        Result:


Test Data:
13
2 3
4 1
5 1
2 3
6 1
3 2
7 2
2 3
8 3
2 3
2 3
1 4
0 5

//9

17
2 3
4 1
5 1
2 3
6 1
3 2
7 2
7 2
2 3
8 3
2 3
2 3
9 4
9 4
9 4
10 5
10 5

// 9

9
5 1
7 2
7 2
8 3
9 4
9 4
9 4
10 5
10 5

// 8

//----------------------------------------------------------------------------*/

#include <iostream>
#include <string.h>
using namespace std;
const int maxTime = 100002, maxShift = 13;
int n;
int maxSum, maxCircleTime;
int pie[maxTime][maxShift], dp[maxTime][maxShift];

void numberTower()
{
        int i, j, k;
        for( i = maxCircleTime; i >= 0; i-- )
                for( j = 1; j < 12; j++ )
                {
                        dp[i][j] = max( dp[i+1][j-1], max( dp[i+1][j], dp[i+1][j+1] ) ) + pie[i][j];
                }
        maxSum = dp[0][6];
}

int main()
{
        int i, j, k, point, t;
        while( cin >> n && n )
        {
                memset( pie, 0, sizeof( pie ) );
                memset( dp, 0, sizeof( dp ) );
                // 输入的同时制成一张数塔表
                maxCircleTime = 0;
                for( i = 1; i <= n; i++ )
                {
                        cin >> point >> t;
                        // 数塔表外部循环的最大循环次数由输入的最大时间决定
                        if( maxCircleTime < t )
                                maxCircleTime = t;
                        // point + 1 使位置轴向右移一个单位从而产生了边界0 和12
                        // 方便了数塔表的处理，避免了边界检查
                        ++pie[t][point + 1];
                }
                numberTower();
                cout << maxSum << endl;
        }
}