HDU 1176 免费馅饼

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<cmath>
 4 #include<iostream>
 5 using namespace std;
 6 int dp[100001][11];
 7 int main()
 8 {
 9     int i, j, n, x, t, MaxT;
10     int point = 5;
11     while(~scanf("%d", &n), n)
12     {
13         MaxT = -1;
14         memset(dp, 0, sizeof(dp));
15         for(i = 0; i < n; i++){
16             scanf("%d%d", &x, &t);
17             dp[t][x]++;
18             if(t > MaxT) MaxT = t;
19         }
20         for(t = MaxT; t >=0; t--){//t从最大开始，如果t从0开始，会遇到0-1的情况
21             for(i = 0; i < 11; i++){
22                     if(i == 0){
23                         dp[t][i] += max(dp[t+1][i], dp[t+1][i+1]);//
24                     }
25                     else{
26                         dp[t][i] += max(max(dp[t+1][i], dp[t+1][i+1]), dp[t+1][i-1]);
27                     }
28                 }
29         }
30         printf("%d\n", dp[0][5]);
31     }
32     return 0;
33 }