这题一开始没想到数塔,嘻嘻;由于是学校DIY里面的题目,所以百度了一下题目,拿到了题目测试数据,用来给freopen用的;
不小心瞄到数塔..不过再想想应该也是可以想到的..分析一下就懂了..
值得一提的是自己被题目骗了..最后一个输入的不一定是最大的时间..耽搁了一会- -找了半天原因嘞;//还有需要记得一点的是:正面不好做可以逆着做,像Super jumping 这类的.
读入数据的时候将每个位置+1,为了统一方法; //把a数组去掉可以将时间从93ms下调至46MS;
下面给出代码:
1 #include<iostream> 2 #define maxn 100010 3 int n,a[13][maxn],dp[13][maxn];//位置,时间 4 using namespace std; 5 int max(int a,int b,int c) 6 { 7 int d=a>b?a:b; 8 return c>d?c:d ; 9 } 10 int main() 11 { 12 //freopen("1176.txt","r",stdin); 13 int i,j; 14 while(~scanf("%d",&n),n) 15 { 16 memset(a,0,sizeof(a)); 17 memset(dp,0,sizeof(dp)); 18 int i,j,b=0,t,x; 19 for(i=1;i<=n;i++) 20 { 21 scanf("%d%d",&x,&t); 22 a[x+1][t]+=1; 23 if(b<t) b=t; 24 } 25 for(i=0;i<12;i++) 26 for(j=0;j<maxn;j++) 27 dp[i][j]=a[i][j]; 28 for(i=b-1;i>=0;i--) 29 for(j=1;j<12;j++) 30 dp[j][i]+=max(dp[j-1][i+1],dp[j][i+1],dp[j+1][i+1]); 31 32 printf("%d ",dp[6][0]); 33 34 } 35 return 0; 36 }