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

点击量：241

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

目录

题目描述

\(\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;
}