https://www.luogu.com.cn/record/115075366

https://www.luogu.com.cn/record/115076170

详见注释

#include<bits/stdc++.h>
using namespace std;
const int N=10005,M=1005;
struct Node
{
	int x,low,high;
}stand[N];
int cnt=0;
bool operator <(const Node i,const Node j)
{
	return i.x<j.x;
} 
int x[N],y[N],n,m,k;
int dp[N][M];//dp[i][j]表示从第0列到达地i列高度为j的地方，点击次数最小值 
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<=k;i++)scanf("%d%d%d",&stand[i].x,&stand[i].low,&stand[i].high);
	sort(stand+1,stand+1+k);//对柱子进行排序 
	memset(dp,0x3f,sizeof(dp));
	for(int i=1;i<=m;i++)dp[0][i]=0;//横坐标为0的
	if(stand[1].x==0)//判断第0列有没有柱子 
	{
		for(int i=0;i<=stand[1].low;i++)dp[0][i]=0x3f3f3f3f;
		for(int i=stand[1].high;i<=m;i++)dp[0][i]=0x3f3f3f3f;
		cnt++;
	}
	for(int i=1;i<=n;i++)
	{
		for(int j=x[i];j<m;j++)dp[i][j]=min(dp[i][j],min(dp[i-1][j-x[i]],dp[i][j-x[i]])+1);//往上跳了一次（01背包）或多次（完全背包） 
		for(int j=m-x[i];j<m;j++)dp[i][m]=min(dp[i][m],min(dp[i-1][j],dp[i][j])+1);//跳到天花板上的特判 
		for(int j=1;j+y[i]<=m;j++)dp[i][j]=min(dp[i][j],dp[i-1][j+y[i]]);//往下掉 
		if(stand[cnt+1].x==i)//把柱子上的点清理掉 
		{
			cnt++;
			for(int k=0;k<=stand[cnt].low;k++)dp[i][k]=0x3f3f3f3f;
			for(int k=stand[cnt].high;k<=m;k++)dp[i][k]=0x3f3f3f3f;
		}
		int flag=1;
		for(int j=1;j<=m;j++)flag&=(dp[i][j]==0x3f3f3f3f);//如果到达不了这一列，那么输出0 
		if(flag)return printf("0\n%d",cnt-1),0;
	}
	int ans=0x3f3f3f3f;
	for(int i=0;i<=m;i++)ans=min(ans,dp[n][i]);
	return printf("1\n%d",ans),0;
}