洛谷1941 飞扬的小鸟

题意

有一个长为 $n(\le 10000)$ ，高为 $m(\le 1000)$ 的游戏场景。玩Flappy Bird，在位置 $i$ 点一下会上升 $x_i$ ，否则会下降 $y_i$ ，手速极快每秒可以点多下。有 $k$ 个位置有管道，其中空隙的范围为 $[L_i,H_i]$ 。

可以从位置 $0$ 的任意高度出发，问至少要点几次才能到位置 $n$ ？如果无法到达，最多能跨过多少个管道？

题解

方程贼简单，细节贼恶心系列。

用 $f[i][j]$ 表示到了位置 $i$ ，高度为 $j$ 的最少点击次数。上升为完全背包：

$$f[i][j]=\min(f[i-1][j-x_i],f[i][j-x_i])+1$$

有个细节就是有天花板，所以可以将枚举的上限改为 $m+x_i$ ，然后 $f[i][m]=\min_{j=m}^{m+x_i} f[i][j]$ 。

下降为0/1背包：

$$f[i][j]=\min(f[i][j],f[i-1][j+y_i])$$

然后再将两端管道给赋值成 $inf$ 。

注意转移不能只转移中间部分，这样会造成完全背包的答案不准确。

最后判断答案就比较显然了，详见注释。

#include<bits/stdc++.h>
#define ll long long

using namespace std;

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

const int N=10005,M=1005,inf=0x3f3f3f3f;
bool ex[N];
int n,m,k,a,x[N],y[N],l[N],h[N],f[N][M<<1];

signed main()
{
    n=read(); m=read(); k=read();
    for (int i=1;i<=n;i++)
    {
        x[i]=read(); y[i]=read();
        l[i]=0; h[i]=m+1;
    }
    for (int i=1;i<=k;i++)
    {
        a=read();
        ex[a]=1; //有管道
        l[a]=read(); h[a]=read();
    }
    memset(f,0x3f,sizeof(f));
    for (int j=1;j<=m;j++) f[0][j]=0;
    for (int i=1;i<=n;i++)
    {
        for (int j=1;j<=x[i]+m;j++) f[i][j]=min(f[i][j-x[i]]+1,f[i-1][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<=l[i];j++) f[i][j]=inf; //将管道的部分赋值inf
        for (int j=h[i];j<=m;j++) f[i][j]=inf;
    }
    int ans=inf;
    for (int j=1;j<=m;j++) ans=min(ans,f[n][j]);
    if (ans<inf) return !printf("1\n%d",ans); //能到达
    ans=0;
    for (int i=1;i<=n;i++)
    {
        int mn=inf;
        for (int j=1;j<=m;j++) mn=min(mn,f[i][j]);
        if (mn==inf) break; //无法到达退出
        if (ex[i]) ans++; //跨过的管道数+1
    }
    return !printf("0\n%d",ans);
}