【算法系列学习】[kuangbin带你飞]专题十二基础DP1 G

https://vjudge.net/contest/68966#problem/G

正解一：

http://www.clanfei.com/2012/04/646.html

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<string>
 5 #include<algorithm>
 6 #include<cmath>
 7 #define INF 0x3f3f3f3f
 8 using namespace std;
 9 const int maxn=1e5+1;
10 int a[11][maxn];
11 int dp[11][maxn];
12 
13 bool check(int x)
14 {
15     if(x>=0&&x<=10)
16     {
17         return 1;
18     }
19     return 0;
20 }
21 int main()
22 {
23     int n,x,y,maxtime;
24     while(scanf("%d",&n)==1&&n)
25     {
26         maxtime=-INF;
27         memset(a,0,sizeof(a));
28         for(int i=0;i<n;i++)
29         {
30             scanf("%d%d",&x,&y);
31             a[x][y]++;
32             maxtime=max(maxtime,y);
33         }
34         memset(dp,0,sizeof(dp));
35         for(int i=maxtime-1;i>=0;i--)
36         {
37             for(int k=0;k<=10;k++)
38             {
39                 dp[k][i]=dp[k][i+1];
40                 if(check(k-1))
41                 {
42                     dp[k][i]=max(dp[k][i],dp[k-1][i+1]);
43                 }
44                 if(check(k+1))
45                 {
46                     dp[k][i]=max(dp[k][i],dp[k+1][i+1]);
47                 }
48                 dp[k][i]+=a[k][i];
49             }
50         }
51         printf("%d
",dp[5][0]);
52     }
53     return 0;
54 }

正推

正解二：

http://blog.csdn.net/qq_32680617/article/details/51057963

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<string>
 5 #include<algorithm>
 6 #include<cmath>
 7 #define INF 0x3f3f3f3f
 8 using namespace std;
 9 const int maxn=1e5+5;
10 int a[11][maxn];
11 int main()
12 {
13     int n,x,y;
14     while(scanf("%d",&n)==1&&n)
15     {
16         memset(a,0,sizeof(a));
17         int maxtime=-INF;
18         for(int i=0;i<n;i++)
19         {
20             scanf("%d%d",&x,&y);
21             maxtime=max(maxtime,y);
22             a[x][y]++;
23         }
24         for(int i=maxtime-1;i>=0;i--)
25         {
26             for(int k=0;k<=10;k++)
27             {
28                 if(k==0)
29                 {
30                     a[k][i]+=max(a[k][i+1],a[k+1][i+1]);
31                 }
32                 else
33                 {
34                     a[k][i]+=max(max(a[k][i+1],a[k-1][i+1]),a[k+1][i+1]);
35                 }
36             }
37         }
38         printf("%d
",a[5][0]);
39     }
40     return 0;    
41 }

逆推

RE：

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<string>
 5 #include<algorithm>
 6 #include<cmath>
 7 #define INF 0x3f3f3f3f
 8 using namespace std;
 9 const int maxn=1e5+5;
10 int a[11][maxn];
11 int main()
12 {
13     int n,x,y;
14     while(scanf("%d",&n)==1&&n)
15     {
16         memset(a,0,sizeof(a));
17         int maxtime=-INF;
18         for(int i=0;i<n;i++)
19         {
20             scanf("%d%d",&x,&y);
21             maxtime=max(maxtime,y);
22             a[x][y]++;
23         }
24         for(int i=maxtime-1;i>=0;i--)
25         {
26             for(int k=0;k<=10;k++)
27             {
28                 if(k==0)
29                 {
30                     a[k][i]+=max(a[k][i+1],a[k+1][i+1]);
31                 }
32                 else
33                 {
34                     a[k][i]+=max(max(a[k][i+1],a[k-1][i+1]),a[k+1][i+1]);
35                 }
36             }
37         }
38         printf("%d
",a[5][0]);
39     }
40     return 0;    
41 }

这份代码是按逆推写的，然而不知道为什么RE，看数组也没越界.....先放在这里.....

【算法系列学习】[kuangbin带你飞]专题十二 基础DP1 G

【算法系列学习】[kuangbin带你飞]专题十二基础DP1 G