这是一道非常好的背包题……
我们发现，如果把每次上升和下降操作看为一件物品的话，那么实际上上升的操作对应的是一个完全背包模型，下降操作对应的是01背包模型。
这样的话就有了大致的思路了。我们用dp[i][j]表示从起始点到坐标为（i，j）的点所需要的最少触屏次数。设这一次上升高度为x[i],下降高度为y[i].
那么就得到如下转移方程：
dp[i][j] = min(dp[i-1][j-x[i]]+1,dp[i][j-x[i]]+1);
dp[i][j] = min(dp[i-1][j+y[i]],dp[i][j]);
不过事情还没有结束，我们发现一个问题就是……小鸟在飞到棚顶的时候是不死的……
那我们特判一下dp[i][m]的情况，把所有操作会高出m高度的操作用来更新dp[i][m],即如下转移方程：dp[i][m] = min(dp[i][j],dp[i][m]);
然后就是根本走不到的地方了。这些地方直接全部设为INF即可。
最后判断一下，如果终点任意一点可行即输出结果，否则反向向前找，找到最近的一个无法到达的点，统计之前出现过多少柱子即可。
然后这题有地方很bug，就是对于每个读入的柱子的高度，最低端要+1，最高端要-1，这样才能保证与没有柱子的那些行是同步的。
看一下代码。
#include<cstdio> #include<algorithm> #include<cstring> #include<iostream> #include<cmath> #include<set> #include<queue> #define rep(i,a,n) for(int i = a;i <= n;i++) #define per(i,n,a) for(int i = n;i >= a;i--) #define enter putchar(' ') using namespace std; typedef long long ll; const int M = 10005; const int INF = 1000000009; int read() { int ans = 0,op = 1; char ch = getchar(); while(ch < '0' || ch > '9') { if(ch == '-') op = -1; ch = getchar(); } while(ch >= '0' && ch <= '9') { ans *= 10; ans += ch - '0'; ch = getchar(); } return ans * op; } int n,m,k,x[M],y[M],lo[M],hi[M],f[M][2005],a,b,c,ans = INF,cur,tot,t; bool pd[M],flag; int main() { n = read(),m = read(),k = read(); rep(i,1,n) x[i] = read(),y[i] = read(); rep(i,1,n) lo[i] = 1,hi[i] = m; rep(i,1,k) a = read(),b = read(),c = read(),pd[a] = 1,lo[a] = b+1,hi[a] = c-1; rep(i,0,10000) rep(j,0,2000) f[i][j] = INF; rep(i,1,m) f[0][i] = 0; rep(i,1,n) { rep(j,x[i]+1,x[i]+m) f[i][j] = min(f[i][j-x[i]] + 1,f[i-1][j-x[i]]+1); rep(j,m+1,m+x[i]) f[i][m] = min(f[i][m],f[i][j]); per(j,m-y[i],1) f[i][j] = min(f[i][j],f[i-1][j+y[i]]); rep(j,1,lo[i]-1) f[i][j] = INF; rep(j,hi[i]+1,m) f[i][j] = INF; } rep(j,1,m) ans = min(ans,f[n][j]); if(ans != INF) printf("1 %d ",ans); else { int i,j; for(i = n;i >= 1;i--) { for(j = 1;j <= m;j++) if(f[i][j] < INF) break; if(j <= m) break; } rep(j,1,i) if(pd[j]) tot++; printf("0 %d ",tot); } return 0; }