学步园

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

#include <iostream>
using namespace std;


const int N = 100004;


//dp[i][j]表示在i秒是在j的最大数
//dp[i][j] = max{ dp[i-1][j-1],dp[i-1][j],dp[i-1][j+1] } + a[i][j]
//a[i][j]表示在i秒在j位置的掉饼数
//可以把a[][]赋给dp[][],减少开支


int dp[N][12];


int main()
{
    int n, maxt, t, x;
    int i, tmax;
    while(scanf("%d", &n) && n)
    {
        memset(dp, 0, sizeof(dp));
        maxt = 0;
        for(i = 0; i < n; i++)
        {
            scanf("%d%d",&x, &t);
            if(t > maxt)
                maxt = t;
            dp[t][x]++;
        }


        
        t = maxt;
        for(t --; t >= 0; t--)
        {
            for(i = 0; i <= 10; i++)
            {
                if(i == 0)
                    tmax = max(dp[t + 1][i], dp[t + 1][i + 1]);
                else if(i == 10)
                    tmax = max(dp[t + 1][i], dp[t + 1][i - 1]);
                else
                {
                    tmax = max(dp[t + 1][i - 1], dp[t + 1][i]);
                    tmax = max(tmax, dp[t + 1][i + 1]);
                }
                dp[t][i] += tmax;
            }
        }
        printf("%d\n", dp[0][5]);
    }
    return 0;
}