HDU 1176 免费馅饼

很好的DP题，本质上是数字三角形的变形从5第一层到4 5 6第二层这样可以把可到达的位置分层然后套用数字三角形即可

#include <bits/stdc++.h>
using namespace std;
long long bk[100005][20],f[100005][20];
long long n,m,ans,x,y;
int main()
{
	while(~scanf("%lld",&n))
	{
		if(n==0)
		break;
		m=0,ans=0;
		memset(bk,0,sizeof(bk));
		memset(f,0,sizeof(f));
		for(int i=1;i<=n;i++)
		{
			scanf("%lld%lld",&x,&y);
			bk[y][x]++;
			m=max(m,y);
		}
		for(int j=0;j<=10;j++)
		f[m][j]=bk[m][j];
		for(int i=m;i;i--)
		for(int j=0;j<=10;j++)
		f[i-1][j]=max(f[i][j-1],max(f[i][j],f[i][j+1]))+bk[i-1][j];
		printf("%lld\n",f[0][5]);	 
	}
}