P1941 飞扬的小鸟

蒟蒻zExNocs · 2019-06-03 20:59:36 · 题解

一、杂言

我这个题解是按照从0开始的思路来讲的，比较适合于萌新，可能有些废话，所以请各位大犇们手下留情qwq

二、引入

这个题确实是细节题，毕竟是Noip提高组题还是非常不错的，有一些细节我在这列出来：(下面描述三中的"二中O"就是指这里面的注意点)

①高度为M时不能再上升

②可以多次点击，效果累加【因为无视了这句话写错了很多次QWQ

③管道不是按照顺序输入

④M=0不存在，但是n可以为0，而且鸟可以在(0,0~M)任何一个坐标开始

⑤管道输入的意思是下管道的上边界L与上管道的下边界H，也就是说这个两个管道分别占地为(0,L)和(H,M)

三、思路

这个题给出的状态有很多，那么很明显可以使用动态规划，可以列出的状态有：坐标(x,y)（分别对应目前的长度与高度）、点击次数、是否要点击。

1、状态确定&&转移方程(可以套模板)

假设没有管道，不妨设dp[x][y][p]为上一个点(x-1,?)点击或者不点击转移过来的坐标为(x,y)处的最小点击次数，其中p=1为点击，可以点击多次（二中②）,p=0为不点击。

由题设up[i]为x=i时点击一次上升高度，down[i]为y=i时不点击下降的高度。

那么当p=1时，dp[x][y][1]=min(dp[x-1][y-up[x-1]][0or1],dp[x][y-up[x-1]][1])+1

及要么从上一个点x-1点击一次过来，要么从本x坐标再点一次点出来。

当p=0时，dp[x][y][0]=min(dp[x][y][1],dp[x-1][y+down[x-1]][0or1])

及要么点，要么不点，而且p=0要在p=1已经确定的基础上选择 (即使在后面滚动数组p后也需要这样进行)。

很明显每次选取都是在p=0 or 1中选取最小值，那么可以滚动数组去掉p数组，上状态转移方程其他不变。

但是有一个要求，高度为M时不能再上升（二中①），那么我们可以进行一个特判，如果此时的y>=m，那么上述方程中使y=m，及 dp[x][m]=min(dp[x][m],dp[x][y]),y∈(m,m+up[x-1])

上述x,y都可以进行枚举。那么我们不难看出，去掉p维数组后这个状态方程跟背包神相似，没错，这个就是完全背包+01背包的双组合，那么可以记下: 如果遇见选择或者不选择状态的题目时，可以考虑背包，实在不会可以用我这个笨方法额外设个P数组0,1记录拿不拿状态，然后再优化删除，当然有的题也可能不能删除(这不就是01背包吗！)。

2、探究原题条件

现在又引入了一个叫做管道的鬼东西，那么我们需要再加一个特判。

如果这个地方是管道，也就是说这里不可以通过，那么就使这里的dp[x][y]=inf，不难写出代码：

for(int y=0;y<=low[cnt];y++)
    dp[x][y]=inf;
for(int y=high[cnt];y<=m;y++)
    dp[x][y]=inf;

3、初始化

其实这个应该在状态转移方程里写的，但是我还是单独拉出来了 （其实是作者突然想起来还有初始化，懒得往上插了qwq）

memset(dp,inf,sizeof(dp));
for(int y=1;y<=m;y++)
    dp[0][y]=0;

三句话，没了。不过要注意的是x是从0开始的，所以要初始化在坐标x=0（注意点二中④）

4、判断何时撞墙和最终答案如何输出

很明显，撞的一定是管道上（因为y=0的时候我们根本就没考虑），所以每次在特判管道的时候再查询当前x坐标中dp[x][y]的最小值，如果最小值等于inf的话，那么肯定就撞到这个管道上了，那么此时就输出0和cnt-1。

为什么是cnt-1？，因为你撞到了第cnt个管道，这个管道你过不去，所以当然是通过了cnt-1个管道辣。

如果程序顺利通过的话，那么就直接再次寻找dp[n][y],y∈(1,m)的最小值就可以了。

5、更多优化&&部分代码细节

①、因为状态dp[x][y]一定是由dp[x-1][?]得到,并且dp[x-1][?]在推出dp[x][y]后没有任何作用，所以可以再次滚动数组，定义 i % 2 为x , i%2^1(也可以为((i-1)%2)) 为x-1，那么我们就很愉快的把数组开到 2*max

相比之前的max^2内存少了很多，不过要注意可以去掉上述3中的初始化，改为在枚举x的时候加一条：

for(int y=0;y<=m;j++)
    dp[x%2][y]=inf;

仅仅只是在原来O(n*m)基础上加上了一个m，实际上对时间并没有太大的影响。

②、因为题目已经说明边界为X=0，所以枚举是从X=1的时候进行的，而且每次需要的是up[x-1]，我们不妨在初始化up数组的时候从X=1开始，那么我们使用的就是up[x]而不是up[x-1]了（实际上仅仅只是好看而已,不过也减少了计算量(你觉得计算一个减法能需要多长时间！)）

③、注意开Y数组大小的时候要开大一点，不要只局限于1005，因为咱们并不只是枚举到M，而是要枚举到M+up[x]

④、因为初始化 dp[x][y]=inf ，所以在p=1(虽然p已经被删除了，不过为了方便说明还是把它写出来了)的时候不需要再加一个 dp[x][y]=min(dp[x][y],dp[?][?]+1)的情况，如果要点的话，必须要点一次，否则就是inf

⑤、剩下的细节请看下面的代码，不过代码的部分数组与上述描述的名字不一样（上面的名字是我为了方便讲解取得，下面代码懒得改了qwq）

6、code(你觉得直接抄可以过吗？qwq):

#include<bits/stdc++.h>
using namespace std;
#define ll int
#define gc(a) a=getchar()
#define pc(a) putchar(a)
ll read(){
    char c;ll x=0;bool flag=0;gc(c);
    while(c<'0'||c>'9'){if(c=='-') flag=1;gc(c);}
    while(c>='0'&&c<='9'){x=(x<<3)+(x<<1)+(c^48),gc(c);}
    return flag?-x:x;
}
void pr(ll x){
    if(x<0){x=-x;pc('-');}
    if(x>9) pr(x/10);
    pc(x%10+48);
}
//-------快读------
#define inf 0x3f3f3f3f
const ll maxn=10005;
const ll maxm=10005;
struct node
{
    ll id,h,l;
    bool operator <(const node &a) const
    {
        return id<a.id;
    }
}o[maxn];
ll x[maxn],y[maxn],dp[2][maxm],n,m,k,cnt=1,ans;
int main()
{
    //memset(dp,inf,sizeof(dp));//两个被遗忘的初始化之一qwq
    n=read(),m=read(),k=read();
    for(int i=1;i<=n;i++)
    x[i]=read(),y[i]=read();
    for(int i=1;i<=k;i++)
    o[i].id=read(),o[i].l=read(),o[i].h=read();
    sort(o+1,o+k+1);//管道id排序!
    //for(int i=1;i<=m;i++)
    //dp[0][i]=0;
    for(int i=1;i<=n;i++)
    {
        for(int j=0;j<=m;j++)//注意要初始化！
        dp[i%2][j]=inf;
        for(int j=x[i]+1;j<=x[i]+m;j++)//p=1，完全背包
        dp[i%2][j]=min(dp[i%2^1][j-x[i]]+1,dp[i%2][j-x[i]]+1);
        for(int j=m+1;j<=x[i]+m;j++)//比m大的都是m
        dp[i%2][m]=min(dp[i%2][m],dp[i%2][j]);
        for(int j=1;j<=m-y[i];j++)//p=0，01背包
        dp[i%2][j]=min(dp[i%2][j],dp[i%2^1][j+y[i]]);
        if(i==o[cnt].id)//如果这个地方有管道
        {
            ans=inf;//主要每次都要初始化一次！
            for(int j=0;j<=o[cnt].l;j++)
            dp[i%2][j]=inf;
            for(int j=o[cnt].h;j<=m;j++)
            dp[i%2][j]=inf;
            for(int j=1;j<=m;j++)//寻找是否可以通过
            ans=min(dp[i%2][j],ans);
            if(ans==inf)
            {
                pr(0);pc('\n');pr(cnt-1);return 0;
            }
            cnt++;
        }
    }
    ans=inf;//注意要初始化！
    for(int j=1;j<=m;j++)
    ans=min(dp[n%2][j],ans);
    pr(1);pc('\n');pr(ans);
    return 0v0;
}

4、后语

题解千万条，细节第一条

题解没有赞，作者两行泪

你看作者因为写题解都把上面的数字记成4了，你们忍心咩qwq