免费馅饼

G - 免费馅饼

参考： 免费馅饼~-~（hdu 1176）

思路：刚开始始的时候想dfs，但是数据太多了，而且有些情况也会漏掉。

于是DP是最好的选择，但是DP的时候又要考虑到一点，起始位置是固定的，无法确定最大值与起始位置的联系，所以，需要反着来算，从最后一秒开始计算，对于每一个时间点，每一个位置来说，其 DP 值就是这一秒内该位置掉落的馅饼个数加上 左 中 右 三个位置中的最大值，即可得到该点该时刻的 DP 值。

如果正着 DP 不方便，可以考虑反着 DP。

代码：

// Created by CAD on 2019/10/26.
#include <bits/stdc++.h>
#define mst(name, value) memset(name,value,sizeof(name))
using namespace std;

int dp[100005][15];
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n;
    while(cin>>n,n)
    {
        mst(dp,0);
        int maxt=0;
        for(int i=1,x,t;i<=n;++i)
            cin>>x>>t,dp[t][x+1]++,maxt=max(maxt,t);
        for(int i=maxt-1;i>=0;--i)
            for(int j=1;j<=11;j++)
                dp[i][j]+=max(max(dp[i+1][j-1],dp[i+1][j]),dp[i+1][j+1]);
            cout<<dp[0][6]<<endl;
    }
    return 0;
}