题解 P1941 【飞扬的小鸟 】
让我们好好的仔细地看题
发现。小鸟一次单位时间内向上跳的次数是无限制的（除非飞到天花板）
那么，回去翻翻 背包九讲 你会发现：
上升其实就是一个完全背包问题
而背包容量就是当前小鸟飞到的高度。
这样一想，下降也很好解决了。
在一个单位时间里，小鸟最多只能下降一次。
那么，对应的背包问题就是01背包问题。
思路理顺了，让我们来推一推方程和状态吧
状态：
那么方程呢？
先来想如果是跳，
那么当前位置可能是
-
由前一个单位时间内的
j-x_i 跳了一次得来的 -
由现在的
j-x_i 跳了一次得来的
如果是下降
那么当前的位置可能是
-
不跳（即保持现在的位置）
-
由前一个单位时间内的
j+y_i 降了一次得来的
如果是在顶层
就只要将向上跳时溢出m高度的状态与自己比较，取最小值即可
如果无法通过（即有柱子） 只要附一个极大值即可。（方便后续处理）
就差不多了吧
#include<bits/stdc++.h>
#define N 10005
using namespace std;
int n,m,k,x[N],y[N],low[N],high[N],f[N][2005];
bool flag[N];
int main(){
scanf("%d%d%d",&n,&m,&k);
for (int i=1;i<=n;i++) scanf("%d%d",&x[i],&y[i]);
for (int i=1;i<=n;i++){
high[i]=m;
low[i]=1;
}
//用high和low表示最低能和最高能通过的地方.
//开始什么地方都是能通过的,所以high初始为m,low初始为1.
for (int i=1;i<=k;i++){
int xx,yy,zz;scanf("%d%d%d",&xx,&yy,&zz);
flag[xx]=1;
low[xx]=yy+1;
high[xx]=zz-1;
//注意这里yy和zz要分别减一和加一.
}
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){
printf("1\n%d\n",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++;
printf("0\n%d\n",ans);
//若不能通过，要统计再横坐标为几的时候挂了，将挂之前通过的柱子全部计入答案
return 0;
}如果喜欢，点个赞吧。