洛谷 P1941 NOIp2014提高组 飞扬的小鸟 题解【背包】

作者: wjyyy 分类: DP,背包,解题报告 发布时间: 2018-11-03 20:47

点击量:30

 

    一道送好多分的完全背包题。

 

题目描述

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

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

游戏界面是一个长为\(n\),高为\(m\)的二维平面,其中有\(k\)个管道(忽略管道的宽度)。

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

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

小鸟高度等于\(0\)或者小鸟碰到管道时,游戏失败。小鸟高度为\(m\)时,无法再上升。

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

输入输出格式

输入格式:

第\(1\)行有\(3\)个整数\(n,m,k\),分别表示游戏界面的长度,高度和水管的数量,每两个整数之间用一个空格隔开;

接下来的\(n\)行,每行\(2\)个用一个空格隔开的整数\(X\)和\(Y\),依次表示在横坐标位置\(0\sim n-1\)上玩家点击屏幕后,小鸟在下一位置上升的高度\(X\),以及在这个位置上玩家不点击屏幕时,小鸟在下一位置下降的高度\(Y\)。

接下来\(k\)行,每行\(3\)个整数\(P,L,H\),每两个整数之间用一个空格隔开。每行表示一个管道,其中\(P\)表示管道的横坐标,\(L\)表示此管道缝隙的下边沿高度,\(H\)表示管道缝隙上边沿的高度(输入数据保证\(P\)各不相同,但不保证按照大小顺序给出)。

输出格式:

共两行。

第一行,包含一个整数,如果可以成功完成游戏,则输出\(1\),否则输出\(0\)。

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

输入输出样例

输入样例#1:

10 10 6
3 9
9 9
1 2
1 3
1 2
1 1
2 1
2 1
1 6
2 2
1 2 7
5 1 5
6 3 5
7 5 8
8 7 9
9 1 3
输出样例#1:

1
6
输入样例#2:

10 10 4
1 2
3 1
2 2
1 8
1 8
3 2
2 1
2 1
2 2
1 2
1 0 2
6 7 9
9 1 4
3 8 10
输出样例#2:

0
3

【输入输出样例说明】

如下图所示,蓝色直线表示小鸟的飞行轨迹,红色直线表示管道。

数据规模与约定

对于\(30\%\)的数据:\(5\le n\le 10,5\le m\le 10,k=0\), 保证存在一组最优解使得同一单位时间最多点击屏幕\(3\)次;
对于\(50\%\)的数据:\(5\le n\le 20,5\le m\le 10\),保证存在一组最优解使得同一单位时间最多点击屏幕\(3\)次;
对于\(70\%\)的数据:\(5\le n\le 1000,5\le m\le 100\);
对于\(100\%\)的数据:\(5\le n\le 10000,5\le m\le 1000,0\le k<n,0<X<m,0<Y<m,0<P<n,0\le L<H\le m,L+1<H\)。

题解:

    写过两种错解都拿了75分,感觉数据有点水?因为每一步可以跳很多次或不跳,因此可以转化为一个完全背包问题,只是不花代价转移是需要减少高度的。

    因为横坐标是有限的,所以不用离散化。读入上下管道时可以直接赋给相应坐标,转移时邻项转移就可以了。主要说一下我的错误思路。

    我的思路是从\(i-1\)转移到\(i\),转移范围是\((down_i,up_i)\),也就是只在两个空位之间转移,如下图两个蓝色位置(红色是管道)

    但是这样很容易出现一个问题,在完全背包的转移中,我们首先要转移的位置(即只跳一次)可能会在管道上,而我直接忽略了管道上的转移,保持\(inf\)不变,但是这样是有问题的,因为完全背包转移关系到自己同层,虽然状态不合法,但是也需要为上面的状态进行过渡,这一段可以在当前层DP做完后再置为\(inf\)以示不合法。

    剩下的细节就是在小鸟飞到高度为\(m\)位置的处理了。高度为\(m\)的位置可以从前一格高度为\([m-kX,m](k\in \bf{N^*})\)的位置转移,但是只能下降到\(m-Y\)。这个地方稍微注意一下应该没什么问题。

Code:

#include<cstdio>
#include<cstring>
#include<algorithm>
using std::sort;
using std::min;
int f[10100][1010];
int up[10100],down[10100];
int _up[10100],_down[10100];
int sum[10100];
bool exi[10100];
int main()
{
    memset(f,0x3f,sizeof(f));
    int n,m,k,u;
    scanf("%d%d%d",&n,&m,&k);
    for(int i=1;i<=n;++i)
        scanf("%d%d",&up[i],&down[i]);
    for(int i=0;i<=n;++i)
    {
        _down[i]=0;
        _up[i]=m+1;
    }
    for(int i=1;i<=k;++i)
    {
        scanf("%d",&u);
        scanf("%d%d",&_down[u],&_up[u]);
        exi[u]=1;
    }
    for(int i=1;i<n;++i)
        sum[i]=sum[i-1]+exi[i];
    for(int i=1;i<=m;++i)
        f[0][i]=0;
    for(int i=1;i<=n;++i)
    {
        for(int j=up[i];j<=m;++j)
            f[i][j]=min(f[i-1][j-up[i]]+1,f[i][j-up[i]]+1);
        for(int j=m-up[i];j<=m;++j)
            f[i][m]=min(f[i][m],min(f[i-1][j]+1,f[i][j]+1));
        for(int j=1;j<=m;++j)
            if(j+down[i]<=m)
                f[i][j]=min(f[i][j],f[i-1][j+down[i]]);
        for(int j=1;j<=_down[i];++j)
            f[i][j]=0x3f3f3f3f;
        for(int j=_up[i];j<=m;++j)
            f[i][j]=0x3f3f3f3f;
    }
    int ans=0x3f3f3f3f;
    for(int i=1;i<=m;++i)
        ans=ans<f[n][i]?ans:f[n][i];
    if(ans==0x3f3f3f3f)
    {
        for(int i=n;i;--i)
            for(int j=1;j<=m;++j)
                if(f[i][j]<0x3f3f3f3f)
                {
                    printf("0\n%d\n",sum[i]);
                    return 0;
                }
    }
    printf("1\n%d\n",ans);
    return 0;
}

 

说点什么

avatar
  Subscribe  
提醒
/* */