hdu 1176 免费馅饼

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <algorithm>
 4 #include <cctype>
 5 #include <stdlib.h>
 6 #include <cstring>
 7 #include <string>
 8 using namespace std;
 9 
10 int dp[100003][12];
11 int main()
12 {
13     int n,timend;
14     while(scanf("%d",&n)==1&&n)
15     {
16         int timend=0,ans=0;
17         while(n--)
18         {
19             int x,t;
20             scanf("%d%d",&x,&t);
21             dp[t][x]++;
22             timend=timend<t?t:timend;//record when did the time end
23         }
24         
25         for(int i=timend-1;i>=0;i--)//because timend can not +1,in some situation
26         {
27             for(int j=0;j<=10;j++)//which means from one point marked as j to the end 
28             {                        //and record the bigger number of pies in one pace(next 1s)
29                 if(j==0){
30                     dp[i][j]+=max(dp[i+1][j],dp[i+1][j+1]);//pay attention to the special location like 0,10
31                 }
32                 else if(j==10){
33                     dp[i][j]+=max(dp[i+1][j],dp[i+1][j-1]);
34                 }
35                 else{
36                     dp[i][j]+=max(max(dp[i+1][j],dp[i+1][j-1]),max(dp[i+1][j-1],dp[i+1][j+1]));//2 2 compare,then campare 2 
37                 }
38             }
39         }
40         printf("%dn",dp[0][5]);//because gameboy sat point 5 originally.
41     }
42     
43     return 0;
44 }