首页 > 代码库 > HDU 1176 免费馅饼

HDU 1176 免费馅饼

裸DP,刚开始没想到转化为数字三角形的模型。墨迹了好久。

不过这个题的数据规模真让人蛋疼,T=0是存在的.....



#include<stdio.h>
#include<string.h>

int max (int a, int b, int c)
{
    if (b > a)
	{
		a = b;
	}
    if (c > a)
	{
		a = c;
	}
    return a;
}

int i,j;
int a[100010][15];

int main()
{
	int n;
	while(scanf("%d",&n)!=EOF,n)
	{
		memset(a,0,sizeof(a));
		int x,t;
		int last=0;
		while(n--)
		{
			scanf("%d%d",&x,&t);
			a[t][x+1]++;  // 将数组整体右移 省略边界考虑
			if(t>last)
			{
				last=t; 
			}
		}
		for(i=last;i>=0;i--)
		{
			for(j=1;j<=11;j++)
			{
				a[i][j]+=max(a[i+1][j],a[i+1][j+1],a[i+1][j-1]);
			}
		}
		printf("%d\n",a[0][6]);
	}
	return 0;
}


HDU 1176 免费馅饼