首页 > 代码库 > 南阳613

南阳613

 1 //与数塔一样dp递推即可
 2 #include<cstdio>
 3 #include<cstring>
 4 
 5 int a[100005][11];
 6 
 7 int Max(int a,int b)
 8 {
 9     return a>b?a:b;
10 }
11 
12 int Max(int a,int b,int c)
13 {
14     return Max(a,b)>c?Max(a,b):c;
15 }
16 
17 int main()
18 {
19     int n,maxn;
20     while(~scanf("%d",&n) && n)
21     {
22         maxn = 0;
23         memset(a,0,sizeof a);
24         while(n--)
25         {
26             int x,t;
27             scanf("%d%d",&x,&t);
28             ++a[t][x];
29             if(t > maxn)
30                 maxn = t;
31         }
32         for(int i=maxn-1; i>=0; --i)
33             for(int j=0; j<11; ++j)
34                 if(j == 0)
35                     a[i][j]+=Max(a[i+1][j],a[i+1][j+1]);
36                 else if(j == 10)
37                     a[i][j]+=Max(a[i+1][j],a[i+1][j-1]);
38                 else
39                     a[i][j]+=Max(a[i+1][j],a[i+1][j+1],a[i+1][j-1]);
40         printf("%d\n",a[0][5]);
41     }
42 }

 

南阳613