#include<bits/stdc++.h>
using namespace std;
#define ll int
#define gc(a) a=getchar()
#define pc(a) putchar(a)
ll read(){
    char c;ll x=0;bool flag=0;gc(c);
    while(c<'0'||c>'9'){if(c=='-') flag=1;gc(c);}
    while(c>='0'&&c<='9'){x=(x<<3)+(x<<1)+(c^48),gc(c);}
    return flag?-x:x;
}
void pr(ll x){
    if(x<0){x=-x;pc('-');}
    if(x>9) pr(x/10);
    pc(x%10+48);
}

#define inf 0x3f3f3f3f
const ll maxn=10005;
const ll maxm=10005;
struct node
{
	ll id,h,l;
	bool operator <(const node &a) const
	{
		return id<a.id;
	}
}o[maxn];
ll x[maxn],y[maxn],dp[2][maxm],n,m,k,cnt=1,ans;
int main()
{
	
	n=read(),m=read(),k=read();
	for(int i=1;i<=n;i++)
	x[i]=read(),y[i]=read();
	for(int i=1;i<=k;i++)
	o[i].id=read(),o[i].l=read(),o[i].h=read();
	sort(o+1,o+k+1);

	for(int i=1;i<=n;i++)
	{
		for(int j=0;j<=m;j++)
		dp[i%2][j]=inf;
		for(int j=x[i]+1;j<=x[i]+m;j++)
		dp[i%2][j]=min(dp[i%2^1][j-x[i]]+1,dp[i%2][j-x[i]]+1);
		for(int j=m+1;j<=x[i]+m;j++)
		dp[i%2][m]=min(dp[i%2][m],dp[i%2][j]);
		for(int j=1;j<=m-y[i];j++)
		dp[i%2][j]=min(dp[i%2][j],dp[i%2^1][j+y[i]]);
		if(i==o[cnt].id)
		{
			ans=inf;
			for(int j=0;j<=o[cnt].l;j++)
			dp[i%2][j]=inf;
			for(int j=o[cnt].h;j<=m;j++)
			dp[i%2][j]=inf;
			for(int j=1;j<=m;j++)
			ans=min(dp[i%2][j],ans);
			if(ans==inf)
			{
				pr(0);pc('\n');pr(cnt-1);return 0;
			}
			cnt++;
		}
	}
	ans=inf;
	for(int j=1;j<=m;j++)
	ans=min(dp[n%2][j],ans);
	pr(1);pc('\n');pr(ans);
	return 0^0;
}

#include <bits/stdc++.h>
using namespace std;
#define inf 0x3f3f3f3f
#define ll long long 
const int N=10005,M=1005;//宽度，高度 
int n,m,k,s,t,f[N][M];
struct node{
	int x,y;//上升x高度 下降y高度 
}a[N];
struct node1{
	int id,x,y;//id横坐标，x下边沿高度 y上边沿高度 
	bool operator<(const node1&k)const{
		return id<k.id;
	}
}b[N];
int main()
{
    memset(f,inf,sizeof(f));
  	cin>>n>>m>>k;
  	for (int i=0;i<n;++i)
  		cin>>a[i].x>>a[i].y;
  	for (int i=1;i<=k;++i)
  		cin>>b[i].id>>b[i].x>>b[i].y;
  	sort(b+1,b+1+k);
  	int now=1,bo;
  	for (int i=1;i<=m;++i)
  		f[0][i]=0;
  	for (int i=1;i<=n;++i){
		if (now<=k && b[now].id==i-1){
		//i-1是一个水管列，判断是否合法 
			bo=0;
			for (int j=b[now].x+1;j<b[now].y;++j)
				if (f[i-1][j]<inf){
				//合法区间是否有小于inf的f数组 
					bo=1;
					break;
				}
			if (!bo) {//失败，直接输出答案 
				printf("0\n%d\n",now-1);
				return 0;
			}
			for (int j=1;j<=b[now].x;++j)
			//将被水管覆盖的地方设置为inf 
				f[i-1][j]=inf;
			for (int j=b[now].y;j<=m;++j)
				f[i-1][j]=inf;
			++now;
		}  
		int x=a[i-1].x,y=a[i-1].y;
		for (int j=x+1;j<=m;++j)//按若干次x 
			f[i][j]=min(f[i][j-x],f[i-1][j-x])+1;
		for (int j=m-x;j<=m;++j){//顶部单独处理 
			f[i][m]=min(f[i][m],f[i-1][j]+1);
			f[i][m]=min(f[i][m],f[i][j]+1);
		}
		for (int j=m-y;j>=1;--j)//不按，下降y 
			f[i][j]=min(f[i][j],f[i-1][j+y]);
	}
	int ans=inf;
	for (int i=1;i<=m;++i)
		ans=min(ans,f[n][i]);
	printf("1\n%d\n",ans);
  	
  	
}

f[i,j]表示到第i列时高度为j时跳的最少次数。

这里的j我们从b[i][0]+1开始到b[i][1]-1，只考虑每一列不被水管遮挡的位置的情况

一.先考虑向上跳(先上先下都可以)

j分两类讨论

1.j!=m时，就是一个完全背包，枚举k, k*x[i-1]<j时，即前一列跳k次到达当前这一列

2.j==m时，前一列跳若干次一直跳到高度m(注意前一列高度为m也能跳过来，相当于平移)，跳到m可以刚好跳到或者跳出了被挡在m。

代码忽略了前一列是否是水管的遮挡的位置的判断，假设前一列任意高度都能跳到我们当前这个高度，那么由于我们每一列j枚举的都是无水管遮挡的情况(被遮挡的就是inf)，所以前一列被遮挡的高度必然是inf，所以当前列的f[i,j]要想被更新，f[i-1][j-k*x[i-1]必须是合法情况，否则f[i,j]依然是inf。

二.向下掉落一次

没什么好说的。

#include <bits/stdc++.h>
using namespace std;
const int N=1e4+10,M=3e3+10;
int f[N][M];
int n,m,k;
int x[N],y[N];
int b[N][2];
int sum[N];
int main(){
	
	cin>>n>>m>>k;
	
	for(int i=0;i<n;i++){
		cin>>x[i]>>y[i];
	}
	for(int i=0;i<=n;i++)
		b[i][0]=0,b[i][1]=m+1;
	
	for(int i=1;i<=k;i++){
		int p,l,h;
		cin>>p>>l>>h;
		b[p][0]=l,b[p][1]=h;
		sum[p]=1;
	}
	for(int i=1;i<=n;i++)sum[i]+=sum[i-1];
	
	memset(f,0x3f,sizeof f);
	for(int i=0;i<=m;i++)f[0][i]=0;
	
	for(int i=1;i<=n;i++){
		
		for(int j=b[i][0]+1;j<b[i][1];j++){
			
			if(j!=m)
				for(int k=1;k*x[i-1]<j;k++){
				
					f[i][j]=min(f[i][j],f[i-1][j-k*x[i-1]]+k);
				}
			else{
				/*for(int k=m-x[i-1];k<=m;k++)
					f[i][j]=min(f[i][j],min(f[i][k]+1,f[i-1][k]+1));*/
				for(int k=1;k<=m;k++){
					int t=(m-k)/x[i-1];
					if((m-k)%x[i-1]||k==m)t++;
					f[i][j]=min(f[i][j],f[i-1][k]+t);
				}
			}
			if(j+y[i-1]<=m)f[i][j]=min(f[i][j],f[i-1][j+y[i-1]]);
		//	cout<<"f["<<i<<"]["<<j<<"]="<<f[i][j]<<"\n";
		}
		//cout<<endl;
	}
	int ans=0x3f3f3f3f;
	
	for(int i=0;i<=m;i++)ans=min(ans,f[n][i]);
	if(ans!=0x3f3f3f3f){
		cout<<1<<endl<<ans;
	}
	else{
		cout<<0<<endl;
		int i,j;
		bool flag=0;
		for(i=n;i>=0;i--){
			for(j=0;j<=m;j++){
				if(f[i][j]!=0x3f3f3f3f){
					flag=1;
					break;
				}
			}
			if(flag)break;
		}
		cout<<sum[i];
	}
}

下面是满分做法，利用完全背包重复利用的性质更新f[i,j]

#include <bits/stdc++.h>
using namespace std;
const int N=1e4+10,M=3e3+10,inf=0x3f3f3f3f;
int f[N][M];
int n,m,k;
int x[N],y[N];
int b[N][2];
int sum[N];
int main(){
	
	cin>>n>>m>>k;
	
	for(int i=0;i<n;i++){
		cin>>x[i]>>y[i];
	}
	for(int i=0;i<=n;i++)
		b[i][0]=0,b[i][1]=m+1;
	
	for(int i=1;i<=k;i++){
		int p,l,h;
		cin>>p>>l>>h;
		b[p][0]=l,b[p][1]=h;
		sum[p]=1;
	}
	for(int i=1;i<=n;i++)sum[i]+=sum[i-1];
	
	memset(f,0x3f,sizeof f);
	for(int i=0;i<=m;i++)f[0][i]=0;
	
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){//忽略非法状态(为什么?因为利用完全背包时要f[i][j-k*x[i-1]]，
		//但j-k*x在此列可能是违法状态，前一列跳若干次到j-k*x，j-k*x再跳k次到j,利用完全背包省去一轮循环
		//所以更新所有的j，以便后面的更大的j能利用它 
		
			if(j!=m){
				if(j>x[i-1])
					f[i][j]=min(f[i][j],min(f[i-1][j-x[i-1]]+1,f[i][j-x[i-1]]+1));
			}		
			else{//j==m时 
				for(int k=m-x[i-1];k<=m;k++)
					f[i][j]=min(f[i][j],min(f[i-1][k]+1,f[i][k]+1));
			}
		}
		for(int j=b[i][0]+1;j<b[i][1];j++)//向下掉落要单独循环一次 
			if(j+y[i-1]<=m)f[i][j]=min(f[i][j],f[i-1][j+y[i-1]]);
		for(int j=0;j<=b[i][0];j++)f[i][j]=inf;//再把非法状态给置成inf 
		for(int j=b[i][1];j<=m;j++)f[i][j]=inf;
	}
	int ans=inf;
	
	for(int i=0;i<=m;i++)ans=min(ans,f[n][i]);
	if(ans!=inf){
		cout<<1<<endl<<ans;
	}
	else{
		cout<<0<<endl;
		int i,j;
		bool flag=0;
		for(i=n;i>=0;i--){
			for(j=0;j<=m;j++){
				if(f[i][j]!=inf){
					flag=1;
					break;
				}
			}
			if(flag)break;
		}
		cout<<sum[i];
	}
}