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

· · 题解

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

题意简述

给定一个游戏界面的高和宽，其中碰到上边界将不能再上升，而碰到下边界会直接死亡。又给定了一些柱子的横坐标和上下边界，小鸟在飞行时只能从中间穿过，不能碰到上下边界。求是否能到达右边。能，则输出最少的点击次数；不能，则输出最多通过的柱子数。

给定每个位置的 up_i, down_i其中小鸟只能向上移动任意次 up_i 或一次 down_i，只有 up_i 需要点击。

思路

90tps

考虑 DP。对于每个位置，我们可以记录到达该位置需要点击的最少次数。设 f_{i,j} 为到达位置 (x, y) 需要点击的最少次数，我们可以推出状态转移方程：

f_{i,j} = \max(f_{i - 1, j - k\times up_{i - 1}} + k, f_{i - 1, j + down_{i - 1}})

由于每个位置只有他的上一个位置转移过来，所以我们自然可以用滚动数组优化（不用也不影响）。时间复杂度 O(n^2)，预计得分 70tps（考场上感觉不少就直接跳过去做下一题了，事实上是 90tps）。

代码


#include<bits/stdc++.h>
using namespace std;
#define ll long long

inline ll read(){ ll res = 0, f = 1; char c = getchar(); while(c > '9' || c < '0'){ if(c == '-')f = -1; c = getchar(); } while(c >= '0' && c <= '9'){ res = res 10 + c - '0'; c = getchar(); } return res f; }

const int N = 100010, M = 10010; ll up[N], down[N]; struct ii{ ll h, l; int ii; }qu[N]; ll f[3][M];

signed main(){ ll n = read(), m = read(), k = read(); for(int i = 0; i < n; i ++){ up[i] = read(), down[i] = read(); } for(int i = 1; i <= k; i ++){ ll x = read(), l = read(), h = read(); qu[x] = {h - 1, l + 1}; } for(int i = 1; i <= n; i ++){ if(qu[i]. h == 0){ qu[i]. h = m; qu[i]. l = 1; qu[i]. ii = qu[i - 1]. ii; } else{ qu[i]. ii = qu[i - 1]. ii + 1; }

}
memset(f, 0x3f, sizeof f);
for(int i = 1; i <= m; i ++){
    f[0][i] = 0;
}
qu[0] = {m, 1};
for(int i = 0; i < n; i ++){
    bool flag = 0;
    for(int j = 1; j <= m; j ++)f[(i + 1) & 1][j] = 0x3f3f3f3f3f3f3f3f;
    for(int j = qu[i]. l; j <= qu[i]. h; j ++){
        if(f[i & 1][j] == 0x3f3f3f3f3f3f3f3f)continue;

        if(j - down[i] >= qu[i + 1]. l && j - down[i] <= qu[i + 1]. h){
            f[(i + 1) & 1][j - down[i]] = min(f[(i + 1) & 1][j - down[i]], f[i & 1][j]);
            flag = 1;
        }
        if(qu[i + 1]. h < qu[i]. l)continue;
        ll sta = (qu[i + 1]. l - j) / up[i];
        if((qu[i + 1]. l - j) % up[i])sta ++;
        sta = max(1ll, sta);
        ll endd = (qu[i + 1]. h - j) / up[i];
        if(qu[i + 1]. h == m && (qu[i + 1]. h - j) % up[i]){
            endd ++;
        }

        for(int k = sta; k <= endd; k ++){
            ll hh = min(m, j + up[i] * k);
            flag = 1;
            f[(i + 1) & 1][hh] = min(f[(i + 1) & 1][hh], f[i & 1][j] + k);

        }
    }
    if(!flag){
        cout << 0 << endl << qu[i]. ii;
        return 0;
    }
}

ll ans = 0x3f3f3f3f3f3f3f3f;
for(int j = qu[n]. l; j <= qu[n]. h; j ++){
    ans = min(ans, f[n & 1][j]);
}
cout << 1 << endl;
cout << ans;
return 0;

}

### 100tps
我们观察上升和下降的规则，可以发现，上升的过程和完全背包有着惊人的相似度，而下降的过程几乎就是我们熟悉的 $01$ 背包。由此，我们可以得出一个做法：将上升和下降分开处理，分别做完全和 $01$ 背包。

完全背包（上升）的第二次以及更多的点击可以直接从
$f_{i, j - up_{i - 1}}$ 转移，只有点一次是从 $f_{i-1,j - up_{i-1}}$ 转移的（完全背包 $n^2$ 法）；而 $01$ 背包是从 $f_{i - 1, j - up_{i - 1}}$ 转移的。

记得特判一下顶到最上面的情况。
### 代码
```cpp
#include<bits/stdc++.h>
#define N 10005
using namespace std;
#define ll long long
int n,m,k,x[N],y[N],low[N],high[N],f[N][2005];
bool flag[N];

inline ll read(){
    ll res = 0, f = 1;
    char c = getchar();
    while(c > '9' || c < '0'){
        if(c == '-')f = -1;
        c = getchar();
    }
    while(c >= '0' && c <= '9'){
        res = res * 10 + c - '0';
        c = getchar();
    }
    return res * f;
}

int main(){
    n = read(), m = read(), k = read();
    for (int i = 1; i <= n; i ++) x[i] = read(), y[i] = read();
    for (int i = 1; i <= n; i ++){
        high[i] = m;
        low[i] = 1;
    }
    for (int i=1;i<=k;i++){
        int xx = read(), yy = read(), zz = read();
        flag[xx] = 1;
        low[xx] = yy + 1;
        high[xx] = zz - 1;
    }
    memset(f, 0x3f3f3f, sizeof(f));
    for (int i = 1; i <= m; i ++) f[0][i]=0;
    for (int i = 1; i <= n; i ++){
        for (int j = x[i] + 1; j <= x[i] + m; j ++) 
            f[i][j] = min(f[i - 1][j - x[i]] + 1, f[i][j - x[i]] + 1);
        for (int j = m + 1; j <= x[i] + m; j ++)
            f[i][m] = min(f[i][m], f[i][j]);
        for (int j = 1; j <= m - y[i]; j ++)
            f[i][j] = min(f[i][j], f[i - 1][j + y[i]]);
        for (int j = 1;j < low[i]; j ++)
            f[i][j] = 0x3f3f3f;
        for (int j = high[i] + 1; j <= m; j++)
            f[i][j] = 0x3f3f3f;
    }
    int ans=0x3f3f3f;
    for (int i = 1;i <= m; i ++) ans = min(ans, f[n][i]);
    if (ans < 0x3f3f3f){
        cout << 1 << endl << ans;
        return 0;
    }
    int i, j;
    for (i = n; i >= 1; i --){
        for (j = 1; j <= m; j ++)
            if (f[i][j] < 0x3f3f3f) break;
        if (j <= m) break;
    }
    ans = 0;
    for (j = 1;j <= i; j ++)
        if (flag[j]) ans ++;
    cout << 0 << endl << ans;
    return 0;
}