hdu1176+dp+数塔

给定0~10 的一个线段 初始在点5上，只能向左右走一格 每个时间段 都会掉一个馅饼  问最多的馅饼

开始以为是区间dp 后面想了一下不是 先处理出模型来 数塔模型 在倒着求

#include <iostream>
#include <algorithm>
#include <stdio.h>
#define INF 0x3f3f3f3f
const int Maxn=100005;
using namespace std;
int f[11][Maxn],n,x,t;
int ()
{
	while(~scanf("%d",&n) && n)
	{
		int Mx=-1;
		memset(f,0,sizeof(f));
		for(int i=1;i<=n;i++){
			scanf("%d%d",&x,&t);
			f[x][t]++;
			if(t>Mx) Mx=t;
		}
		for(int i=Mx-1;i>=0;i--)
		{
			f[0][i]+=max(f[0][i+1],f[1][i+1]);
			f[10][i]+=max(f[10][i+1],f[9][i+1]);
			for(int j=1;j<=9;j++)
				f[j][i]+=max(f[j-1][i+1],max(f[j][i+1],f[j+1][i+1]));
		}
		printf("%dn",f[5][0]);
	}
	return 0;
 }