HDU 1176 免费馅饼 动态规划

数塔问题的变形，每一层代表一秒，但要注意下一秒到这一秒，除了左右外还有自己本身这个位置，不能忽略即dp[i][j]=max{dp[i+1][j-1],dp[i+1][j],dp[i+1][j+1]}

#include <iostream>
using namespace std;
int dp[100002][12];
int max(int a,int b)
{
	return a>b?a:b;
}
int main(){
	int n,i,j,maxt;
	int x,t;
	while(scanf("%d",&n),n!=0)
	{
		maxt = 0;
		memset(dp,0,sizeof(dp));
		for (i = 0;i < n;i++)
		{
			scanf("%d%d",&x,&t);
			dp[t][x]++;
			if (maxt<t)
			{
				maxt=t;
			}
		}
		for (i = maxt-1;i>=0;i--)
		{
			dp[i][0]+=max(dp[i+1][1],dp[i+1][0]);
			for (j = 1;j < 11;j++)
			{
				dp[i][j]+=max(max(dp[i+1][j-1],dp[i+1][j+1]),dp[i+1][j]);
			}
		}
		printf("%d/n",dp[0][5]);
	}
	return 0;
}