题面

像素鸟有毒

解题思路

动态规划，注意一些细节

分析

考虑 $DP$，转移状态有两种，一种就是点击屏幕，一种不点击屏幕，可以看出：前者类似完全背包，后者类似0/1背包

因此只要写两个 $DP$ 即可，然而 $author$ 将两种背包混合在了一起，并且使用了滚动数组（= WA × inf

Warning

1、做完全背包的时候不能先将无法到达的状态赋 $inf$！！！

2、注意点击后超出 $m$ 的情况

PS：貌似题目所说从 任意整数开始 不包括 $0$（$author$ 没打 $0$，但过了

Code

已删去部分无用的板子

#include<bits/stdc++.h>
#define rgt register
#define rint rgt int
#define inf 0x7f7f7f7f
#define N 10007
#define M 1007
using namespace std;
template<class K>inline bool cmin(K&a,const K&b){return (a>b)?a=b,1:0;}
struct node{
    int p,bt,tp;
    inline bool operator< (const node x) const{
        return p<x.p;
    }
}b[N];
int n,m,k,f[M][2],p,c,t,rs[N],dr[N],rse,drp,ans=inf;
int main()
{
    rint i,j,l,r,flg;
    n=read(),m=read(),k=read();
    for(i=1;i<=n;i++) rs[i]=read(),dr[i]=read();//单次点击后上升的高度，否则下降的高度
    for(i=1;i<=k;i++) b[i].p=read(),b[i].bt=read(),b[i].tp=read();//存管道
    sort(b+1,b+k+1),t=1;//按横坐标排序
    for(i=1;i<=n;i++) {
        c=p^1,rse=rs[i],drp=dr[i],flg=1;//flg用于判断是否能完成游戏，当所有状态都无法到达时为1
        for(j=1;j<=m;j++) f[j][c]=inf;
        if(b[t].p==i) {//这是关键，也是易错点
            l=b[t].bt,r=b[t].tp,++t;
            for(j=rse+1;j<r;j++) cmin(f[j][c],min(f[j-rse][p],f[j-rse][c])+1);//完全背包
            for(j=1;j<=l;j++) f[j][c]=inf;//删去碰到管道的情况
            for(;j<r;j++) {//0/1背包
                if(j+drp<=m) cmin(f[j][c],f[j+drp][p]);
                if(j>l) flg&=(f[j][c]>=inf);
            }
        }
        else {
            for(j=1;j<=m;j++) {//没有管道的转移可以同时一起
                k=min(j+rse,m),cmin(f[k][c],min(f[j][p],f[j][c])+1);
                if(j+drp<=m) cmin(f[j][c],f[j+drp][p]);
                flg&=(f[j][c]>=inf);
            }
        }p=c;
        if(flg) {printf("0\n%d",t-2);return 0;}//无法完成则输出最多能过的柱子数
    }
    for(i=1;i<=m;i++) cmin(ans,f[i][p]);
    printf("1\n%d",ans);
    return 0;
}

另附某题解代码，自认为层次比 $author$ 的清晰

//by @ZMYJOE(Luogu)
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int maxn=10000+10;
const int maxm=2000+10;
int n,m,p;
int x[maxn],y[maxn];   //i位置，上升x[i],下降y[i] 
int low[maxn],high[maxn];   //i位置能通过的范围是low[i]-high[i] 
int f[maxn][maxm];   //到(i,j)的最少点击次数 
bool e[maxn];    //e[i]表示i位置有没有管道 
int main() {
    scanf("%d%d%d",&n,&m,&p);
    for(int i=1; i<=n; ++i) scanf("%d%d",&x[i],&y[i]);
    for(int i=1; i<=n; ++i) {
        low[i]=1;
        high[i]=m;
    }
    int a,b,c;
    for(int i=1; i<=p; ++i) {
        scanf("%d%d%d",&a,&b,&c);
        e[a]=1;
        low[a]=b+1;
        high[a]=c-1;
    }
    memset(f,0x3f,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<=m+x[i]; ++j)
            f[i][j]=min(f[i-1][j-x[i]]+1,f[i][j-x[i]]+1);
        for(int j=m+1; j<=m+x[i]; ++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]=f[0][0];   //不能通过(INF) 
        for(int j=high[i]+1; j<=m; ++j)
            f[i][j]=f[0][0];   //不能通过(INF)
    }
    int ans=f[0][0];
    for(int j=1;j<=m;++j) {
        ans=min(ans,f[n][j]);
    }
    if(ans<f[0][0]) printf("1\n%d\n",ans);
    else{
        int i,j;
        for(i=n;i>=1;i--) {
            for(j=1;j<=m;++j) {
                if(f[i][j]<f[0][0]) break;
            }
            if(j<=m) break;
        }
        ans=0;
        for(int j=1;j<=i;++j) {
            if(e[j]) ans++;
        }
        printf("0\n%d\n",ans);
    }
    return 0;
}

devil.