学步园

http://acm.hdu.edu.cn/submit.php?pid=1176

数塔问题！

这道题注意t可以等于0

数组一定要注意，不要开小了！！！

递推的方式来构造算法！

#include <iostream>
using namespace std;
int dp[100010][11];
int v[100010][11];
int max(int x,int y){
	if(x>y) return x;
	else return y;
}
int max(int x,int y,int z){
	if(x<y) swap(x,y);
	if(x<z) swap(x,z);
	return x;
}
int main()
{
	int n,i,j;
	int x,T;
	int max_T;
	while(scanf("%d",&n)&&n){	
		memset(dp,0,sizeof(dp));	
		memset(v,0,sizeof(v));
		max_T=0;
		for(i=1;i<=n;i++){
			scanf("%d%d",&x,&T);
			v[T][x]++;
			max_T=max(T,max_T);
		}		
		for(i=0;i<11;i++)
			dp[max_T][i]=v[max_T][i];
		for(i=max_T-1;i>=0;i--)
			for(j=0;j<11;j++){
				if(j==0) dp[i][j]=v[i][j]+max(dp[i+1][j],dp[i+1][j+1]);
				else if(j==10) dp[i][j]=v[i][j]+max(dp[i+1][j],dp[i+1][j-1]);
				else dp[i][j]=v[i][j]+max(dp[i+1][j],dp[i+1][j-1],dp[i+1][j+1]);
			}
		cout<<dp[0][5]<<endl;
	}
	return 0;
}