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

洛谷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开始没有太大什么差别,主要看的是存储的位置和运算的位置对的上吗洛谷P1941 [NOIP2014 提高组] 飞扬的小鸟

    注意看图,这里有长度为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中添加循环,都是差不多的。

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

上一篇:$Noip2014/Luogu2312$ 解方程


下一篇:208. 实现 Trie (前缀树)