HDU 1176 免费馅饼

题意：中文题目不解释。

思路：因为是从中间出发所以思路卡了许久，还在之前做了道HIHO入门的题。能想到的点，从时间思考，然后初始化1s的时候，4，5，6，的数值要特别赋值。之后就是统一的2-maxtime时间内，到当前位置就有能移动的三种情况，左移，右移，停留，比较前一秒情况的最大值+当前位置时间的馅饼值（maps[i][j]），最后求最大馅饼值得时候，要从maxtime来求。

dp[i][j] = max(dp[i-1][j],dp[i-1][j-1],dp[i-1][j+1])+maps[i][j]

（maps[i][j]为当前所在位置所能获得的馅饼值）

/**

Sample Input

6

5 1

4 1

6 1

7 2

7 2

8 3

0

Sample Output

4

**/

#include <cstdio>

#include <cstring>

#include <utility>

#include <algorithm>

using namespace std;

const int maxn = 100005;

int n;

int dp[maxn][15]; //二维注意不要爆内存，列大小填15就可以了

int maps[maxn][15];

int main()

{

    while(~scanf("%d",&n)){

        memset(dp,0,sizeof(dp));

        memset(maps,0,sizeof(maps));

        if(!n) break;

        int time = 0;

        for(int i=0;i<n;i++){

            int x,T;

            scanf("%d%d",&x,&T);

            ++maps[T][x];

            time = max(T,time);

        }

        //特殊的1s，特殊处理

        dp[1][4] = maps[1][4];

        dp[1][5] = maps[1][5];

        dp[1][6] = maps[1][6];

        int res = 0;

        //时间2s-maxtime开始算

        for(int i=2;i<=time;i++){

            for(int j=0;j<=10;j++){

                dp[i][j] = max(dp[i-1][j+1],max(dp[i-1][j-1],dp[i-1][j]))+maps[i][j];

            }

        }

        for(int i=0;i<=10;i++)

            res = max(dp[time][i],res);

        printf("%d\n",res);

    }

    return 0;

}