洛谷P1941 [NOIP2014 提高组] 飞扬的小鸟

题目描述

Flappy Bird是一款风靡一时的休闲手机游戏。玩家需要不断控制点击手机屏幕的频率来调节小鸟的飞行高度，让小鸟顺利通过画面右方的管道缝隙。如果小鸟一不小心撞到了水管或者掉在地上的话，便宣告失败。

为了简化问题，我们对游戏规则进行了简化和改编:

游戏界面是一个长为 nn，高为 mm 的二维平面，其中有 kk 个管道（忽略管道的宽度）。

小鸟始终在游戏界面内移动。小鸟从游戏界面最左边任意整数高度位置出发，到达游戏界面最右边时，游戏完成。

小鸟每个单位时间沿横坐标方向右移的距离为 11，竖直移动的距离由玩家控制。如果点击屏幕，小鸟就会上升一定高度 xx，每个单位时间可以点击多次，效果叠加；如果不点击屏幕，小鸟就会下降一定高度 yy。小鸟位于横坐标方向不同位置时，上升的高度 xx 和下降的高度 yy 可能互不相同。

小鸟高度等于 00 或者小鸟碰到管道时，游戏失败。小鸟高度为 mm 时，无法再上升。

现在,请你判断是否可以完成游戏。如果可以，输出最少点击屏幕数；否则，输出小鸟最多可以通过多少个管道缝隙。

输入格式

第 11 行有 33 个整数 n, m, kn,m,k，分别表示游戏界面的长度，高度和水管的数量，每两个整数之间用一个空格隔开；

接下来的 nn 行，每行 22 个用一个空格隔开的整数 xx 和 yy，依次表示在横坐标位置 0 \sim n-10∼n−1 上玩家点击屏幕后，小鸟在下一位置上升的高度 xx，以及在这个位置上玩家不点击屏幕时，小鸟在下一位置下降的高度 yy。

接下来 kk 行，每行 33 个整数 p,l,hp,l,h，每两个整数之间用一个空格隔开。每行表示一个管道，其中 pp 表示管道的横坐标，ll 表示此管道缝隙的下边沿高度，hh 表示管道缝隙上边沿的高度（输入数据保证 pp 各不相同，但不保证按照大小顺序给出）。

输出格式

共两行。

第一行，包含一个整数，如果可以成功完成游戏，则输出 11，否则输出 00。

第二行，包含一个整数，如果第一行为 11，则输出成功完成游戏需要最少点击屏幕数，否则，输出小鸟最多可以通过多少个管道缝隙。

分析：

• 首先因为这道题是一个从最开始，一直到最末尾都有痕可循的，（每一步都可以由上一步推演而来），所以我们可以用动态规划来做
• 上升过程中，鸟可以一个时间段一个飞多次（注意看题，同一时间段上升过程中可以一直不断点击屏幕）-------完全背包
• 下降过程，一个时间段鸟只可以一个下降一次，--------01背包

难点

• 管道，如果此地没有管道？
• 遍历时是从1开始还是从0开始？是 f o r ( i = 1 ; i < = n ; i + + ) for(i=1;i<=n;i++) for(i=1;i<=n;i++)还是 f o r ( i = 0 ; i < = n ; i + + ) for(i=0;i<=n;i++) for(i=0;i<=n;i++)还是 f o r ( i = 0 ; i < n ; i + + ) for(i=0;i<n;i++) for(i=0;i<n;i++)??
• 一直向上飞到顶这个怎么分析

解决

哈哈如果大家遇到了上面的问题，大家不要慌，因为这些问题我也是想了很久才明白的

• 这个在代码中体现

• 其实从0开始和从1开始没有太大什么差别，主要看的是存储的位置和运算的位置对的上吗

  注意看图，这里有长度为10，从0–10有11个点（但是因为末尾是），因为我们用bag[11]来表示这11个点，当 i = 0 i=0 i=0时是最开始这列，当i=10时表示最末尾的这里列。

初级代码1

#include"iostream"
#include"bits/stdc++.h"
using namespace std;
const int maxn=10000+5;
int x[maxn],y[maxn],up[maxn],down[maxn];
int bag[maxn][2005];//背包用来存储数据。
int flag[maxn]={0};//用来判断此地是否有管道
int n,m,k;//long height 水管数量

void dp()
{
    for(int i=1;i<=n;i++){//遍历长度
        if(flag[i]==0){//如果这里没有有管道那么 就改变，up[i],down[i],
                up[i]=m+x[i];
                down[i]=1;
            }
        
        for(int j=down[i];j<=up[i];j++){
            bag[i][j]=min(bag[i][j-x[i]]+1,bag[i-1][j-x[i]]+1);
            //如果用到下次循环用到这个值那么，这个值肯定是最小的，如果是上上升，那么最小值就是本事，如果是下降，那么最小值都一样
            //bag[i][j]=min(bag[i][j],bag[i][j+y[i])//不能这样因为这样 上可能会用到下降 对bag的改变的值
            //if(j>m)bag[i][m]=min(bag[i][j],bag[i][m]);//感觉还是有问题
        }

        for(int j=m+1;j<=x[i]+m;j++)bag[i][m]=min(bag[i][m],bag[i][j]);//超过最高高度
        for(int j=down[i];j<=min(up[i],m);j++){
            if(j+y[i]>m)bag[i-1][j+y[i]]=0x3f3f3f3f;//因为超过了m所以我们，一定是不能够到达的
            bag[i][j]=min(bag[i][j],bag[i-1][j+y[i]]);
        }
    }
    
    //最后的输出

    int ans=0x3f3f3f3f;
    for(int i=1;i<=m;i++)ans=min(bag[n][i],ans);

    if(ans!=0x3f3f3f3f)cout<<1<<endl<<ans;

    else{
        int i,j;
        for(i=n;i>=1;i--){
            for(j=1;j<=m;j++)if(bag[i][j]<0x3f3f3f3f)break;
                if(j<=m)break;//因为如果内循环自然执行结束那么，j==0
        }
        int ans=0;
        for(int kk=1;kk<=i;kk++){
            if(flag[kk]==1)ans++;
        }
        cout<<0<<endl<<ans;
    }
}
int main()
{
    cin>>n>>m>>k;
    for(int i=1;i<=n;i++){
        cin>>x[i]>>y[i];//上升高度，下降高度。
    }
    int x;//横坐标
    for(int i=1;i<=k;i++){
        cin>>x;
        cin>>down[x]>>up[x];//下沿高度，上沿高度
        down[x]++;//假如输入1，那么2可以过
        up[x]--;//假如输入2.那么1可以过
        flag[x]=1;//该位置是否有管道
    }

    memset(bag,0x3f3f3f3f,sizeof(bag));

    for(int i=1;i<=m;i++)bag[0][i]=0;//第一行，进行初始化

    dp();
    return 0;
} 

但是这个代码是有问题的，不够完美

终极代码2

#include"iostream"
#include"bits/stdc++.h"
using namespace std;
const int maxn=10000+5;
int x[maxn],y[maxn],up[maxn],down[maxn];
int bag[maxn][2005];//注意
int flag[maxn]={0};
int n,m,k;//long height 水管数量

void dp()
{
    for(int i=1;i<=n;i++){
          
        for(int j=x[i];j<=x[i]+m;j++)bag[i][j]=min(bag[i][j-x[i]]+1,bag[i-1][j-x[i]]+1);//上升

        for(int j=m+1;j<=x[i]+m;j++)bag[i][m]=min(bag[i][m],bag[i][j]);//超过最高高度，进行处理

        for(int j=1;j<=m-y[i];j++)bag[i][j]=min(bag[i][j],bag[i-1][j+y[i]]);//下降 这个与bag[i][j]进行比较是因为要之前上升达到的位置进行比较

        if(flag[i]==1){//如果这里有水管

            for(int j=1;j<down[i];j++)bag[i][j]=0x3f3f3f3f;

            for(int j=up[i]+1;j<=m;j++)bag[i][j]=0x3f3f3f3f;
        }
        

    int ans=0x3f3f3f3f;
    for(int i=1;i<=m;i++)ans=min(bag[n][i],ans);

    if(ans!=0x3f3f3f3f)cout<<1<<endl<<ans;

    else{
        int i,j;
        for(i=n;i>=1;i--){
            for(j=1;j<=m;j++)if(bag[i][j]<0x3f3f3f3f)break;
                if(j<=m)break;//因为如果内循环自然执行结束那么，j==0
        }
        int ans=0;
        for(int kk=1;kk<=i;kk++){
            if(flag[kk]==1)ans++;
        }
        cout<<0<<endl<<ans;
    }
}
int main()
{
    cin>>n>>m>>k;
    for(int i=1;i<=n;i++){
        cin>>x[i]>>y[i];//上升高度，下降高度。
    }
    int x;//横坐标
    for(int i=1;i<=k;i++){
        cin>>x;
        cin>>down[x]>>up[x];//下沿高度，上沿高度
        down[x]++;//假如输入1，那么2可以过
        up[x]--;//假如输入2.那么1可以过
        flag[x]=1;//该位置是否有管道
    }

    memset(bag,0x3f3f3f3f,sizeof(bag));

    for(int i=1;i<=m;i++)bag[0][i]=0;

    dp();
    return 0;
}

• 大家可以看到终极代码中有很多for但是 但是其实时间复杂度更第一个一样，都是 O ( n 2 ) O(n^2) O(n2),对于已经有n层循环，其实我们在不是最内层for中添加循环，都是差不多的。

大家有什么疑问可以在下方留言