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

工程师子源技术 2022年11月10日

0 收藏 930 点赞 3,318 浏览 1816 个字

正解一：

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

 #include<iostream>
 #include<cstdio>
 #include<cstring>
 #include<string>
 #include<algorithm>
 #include<cmath>
 #define INF 0x3f3f3f3f
 using namespace std;
 const int maxn=1e5+;
 int a[][maxn];
 int dp[][maxn]; bool check(int x)
 {
     if(x>=&&x<=)
     {
         return ;
     }
     return ;
 }
 int main()
 {
     int n,x,y,maxtime;
     while(scanf("%d",&n)==&&n)
     {
         maxtime=-INF;
         memset(a,,sizeof(a));
         for(int i=;i<n;i++)
         {
             scanf("%d%d",&x,&y);
             a[x][y]++;
             maxtime=max(maxtime,y);
         }
         memset(dp,,sizeof(dp));
         for(int i=maxtime-;i>=;i--)
         {
             for(int k=;k<=;k++)
             {
                 dp[k][i]=dp[k][i+];
                 if(check(k-))
                 {
                     dp[k][i]=max(dp[k][i],dp[k-][i+]);
                 }
                 if(check(k+))
                 {
                     dp[k][i]=max(dp[k][i],dp[k+][i+]);
                 }
                 dp[k][i]+=a[k][i];
             }
         }
         printf("%d\n",dp[][]);
     }
     return ;
 }

正推

正解二：

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

 #include<iostream>
 #include<cstdio>
 #include<cstring>
 #include<string>
 #include<algorithm>
 #include<cmath>
 #define INF 0x3f3f3f3f
 using namespace std;
 const int maxn=1e5+;
 int a[][maxn];
 int main()
 {
     int n,x,y;
     while(scanf("%d",&n)==&&n)
     {
         memset(a,,sizeof(a));
         int maxtime=-INF;
         for(int i=;i<n;i++)
         {
             scanf("%d%d",&x,&y);
             maxtime=max(maxtime,y);
             a[x][y]++;
         }
         for(int i=maxtime-;i>=;i--)
         {
             for(int k=;k<=;k++)
             {
                 if(k==)
                 {
                     a[k][i]+=max(a[k][i+],a[k+][i+]);
                 }
                 else
                 {
                     a[k][i]+=max(max(a[k][i+],a[k-][i+]),a[k+][i+]);
                 }
             }
         }
         printf("%d\n",a[][]);
     }
     return ;
 }

逆推

RE：

 #include<iostream>
 #include<cstdio>
 #include<cstring>
 #include<string>
 #include<algorithm>
 #include<cmath>
 #define INF 0x3f3f3f3f
 using namespace std;
 const int maxn=1e5+;
 int a[][maxn];
 int main()
 {
     int n,x,y;
     while(scanf("%d",&n)==&&n)
     {
         memset(a,,sizeof(a));
         int maxtime=-INF;
         for(int i=;i<n;i++)
         {
             scanf("%d%d",&x,&y);
             maxtime=max(maxtime,y);
             a[x][y]++;
         }
         for(int i=maxtime-;i>=;i--)
         {
             for(int k=;k<=;k++)
             {
                 if(k==)
                 {
                     a[k][i]+=max(a[k][i+],a[k+][i+]);
                 }
                 else
                 {
                     a[k][i]+=max(max(a[k][i+],a[k-][i+]),a[k+][i+]);
                 }
             }
         }
         printf("%d\n",a[][]);
     }
     return ;
 }