G - 免费馅饼 (DP&数塔）

思路：从最大时间开始倒序DP，状态转移即由前一时刻周围的三个位置得到。具体看代码。PS：一开始看成1e6，已知MLE。

AC代码：

#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int N=1e5+5;
int dp[N][12];//dp[i][j]第i时刻位置j的最大接到馅饼数. 
int main(){
	int n;
	while(~scanf("%d",&n)&&n){
		memset(dp,0,sizeof dp);//初始化 
		int t_mx=1;
		for(int i=1,x,t;i<=n;i++)
		{
			scanf("%d%d",&x,&t);
			dp[t][x]++;
			t_mx=max(t_mx,t);//找到最大时间 
		}
		for(int i=t_mx-1;i>=0;i--) //时间倒序递推. 
		{
			for(int j=0;j<=11;j++)
			{
				 if(j==0) dp[i][j]+=max(dp[i+1][j],dp[i+1][j+1]);//特判j=0或11. 
				 else if(j==11) dp[i][j]+=max(dp[i+1][j-1],dp[i+1][j]);
				 else dp[i][j]+=max({dp[i+1][j-1],dp[i+1][j],dp[i+1][j+1]});
			}
		}
		printf("%d\n",dp[0][5]);//最后的答案即是回到起点的答案. 
	}
	return 0;
}