这道题是一道隐藏的比较深的DP(我太蒟蒻了！)
设f[i][j]表示到第i列时高度为j的最少步数是多少；
求上升时的方案就是一个完全背包！，求下降时的方案就是一个01背包；
然后处理边界就能A掉；
#include <bits/stdc++.h>
using namespace std;
int n,m,k;
int up[],down[];
int low[],top[],bo[];
int f[][];
int main()
{
cin>>n>>m>>k;
for(register int i=;i<=n;i++){
scanf("%d%d",&up[i],&down[i]);
low[i]=;
top[i]=m;
}
for(register int i=;i<=k;i++){
int a,b,c;
scanf("%d%d%d",&a,&b,&c);
bo[a]=;
low[a]=b+;
top[a]=c-;
}
memset(f,0x3f,sizeof(f));
for(register int i=;i<=m;i++){
f[][i]=;
}
for(register int i=;i<=n;i++){
for(register int j=up[i]+;j<=m+up[i];j++){
f[i][j]=min(f[i][j-up[i]]+,f[i-][j-up[i]]+);
}
for(register int j=m+;j<=m+up[i];j++){
f[i][m]=min(f[i][m],f[i][j]);
}
for(register int j=;j<=m-down[i];j++){
f[i][j]=min(f[i-][j+down[i]],f[i][j]);
}
for(register int j=;j<low[i];j++){
f[i][j]=f[][];
}
for(register int j=top[i]+;j<=m;j++){
f[i][j]=f[][];
}
}
int ans=f[][];
for(register int i=;i<=m;i++){
ans=min(ans,f[n][i]);
}
if(ans<f[][]){
cout<<""<<endl;
cout<<ans<<endl;
}
else{
cout<<""<<endl;
int i,j;
for(i=n;i>=;i--){
for(j=;j<=m;j++){
if(f[i][j]<f[][]){
break;
}
}
if(j<=m){
break;
}
}
ans=;
for(int j=;j<=i;j++){
if(bo[j]) ans++;
}
cout<<ans;
}
}