题意：Flappy Bird 是一款风靡一时的休闲手机游戏。玩家需要不断控制点击手机屏幕的频率来调节小鸟的飞行高度，让小鸟顺利通过画面右方的管道缝隙。如果小鸟一不小心撞到了水管或者掉在地上的话，便宣告失败。为了简化问题，我们对游戏规则进行了简化和改编:游戏界面是一个长为 nn，高为 mm 的二维平面，其中有 kk 个管道（忽略管道的宽度）。 小鸟始终在游戏界面内移动。小鸟从游戏界面最左边任意整数高度位置出发，到达游戏界面最右边时，游戏完成。小鸟每个单位时间沿横坐标方向右移的距离为 11，竖直移动的距离由玩家控制。如果点击屏幕，小鸟就会上升一定高度 xx，每个单位时间可以点击多次，效果叠加；如果不点击屏幕，小鸟就会下降一定高度 yy。小鸟位于横坐标方向不同位置时，上升的高度 xx 和下降的高度 yy 可能互不相同。小鸟高度等于 00 或者小鸟碰到管道时，游戏失败。小鸟高度为 mm 时，无法再上升。现在,请你判断是否可以完成游戏。如果可以，输出最少点击屏幕数；否则，输出小鸟最多可以通过多少个管道缝隙。

其实是一道类似于背包问题的 DP。

状态：f[i][j]f[i][j] 表示横坐标为 ii 时高度为 jj 的最少点击次数。

初始条件：f[0][i]=0(1≤i≤m),f[i][j]=∞(i>0)f[0][i]=0(1\le i\le m),f[i][j]=\infty(i>0)

转移方程：

由于上升可以无数次点击，故选用完全背包的转移方式。

f[i][j]=min⁡(f[i−1][j−x[i]]+1,f[i][j−x[i]]+1)(x[i]+1≤j≤x[i]+m) f[i][j]=\min(f[i-1][j-x[i]]+1,f[i][j-x[i]]+1)(x[i]+1\le j\le x[i]+m)

即当前状态可由前面的坐标点击一次或当前坐标点击一次可得。

同时上升的界限为 mm，故将 mm 的状态特殊处理。

f[i][m]=min⁡(f[i][m],f[i][j])(m+1≤j≤x[i]+m) f[i][m]=\min(f[i][m],f[i][j])(m+1\le j\le x[i]+m)

由于下降只能一次，故采用01背包的转移方式。(注意此时依然正序遍历！！因为当前状态由更高的坐标的状态得到)

f[i][j]=min⁡(f[i][j],f[i−1][j+y[i]])(1≤j≤m−y[i]) f[i][j]=\min(f[i][j],f[i-1][j+y[i]])(1\le j\le m-y[i])

对于管道所处的坐标则赋值为 ∞\infty。

f[i][j]=∞(1≤j<low[i],high[i]+1≤j≤m) f[i][j]=\infty (1\le j<low[i],high[i]+1\le j\le m)

最后答案即为 min⁡(f[n][j])(1≤j≤m)\min(f[n][j])(1\le j\le m)。

如果不能达到终点，那么就倒序遍历横坐标，找到第一个 f[i][j]≠∞f[i][j]\neq \infty 的 ii，并从 1∼i1\sim i 统计管道数即可(可以一开始用一个数组将所有管道的位置标记好)。

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
using namespace std;
int n,m,k;
int x[10101],y[10101];
int low[10101],high[10101];
int f[10101][2010];
bool flag[10101];
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++)
	{
		low[i]=1;
		high[i]=m;
	}
	for(int i=1;i<=k;i++)
	{
		int a,b,c;
		scanf("%d%d%d",&a,&b,&c);
		flag[a]=1;
		low[a]=b+1;
		high[a]=c-1;
	}
	memset(f,0x3f,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]=0x3f3f3f3f;
		for(int j=high[i]+1;j<=m;j++)
			f[i][j]=0x3f3f3f3f;
	}
	int ans=0x3f3f3f3f;
	for(int j=1;j<=m;j++)
		ans=min(ans,f[n][j]);
	if(ans<0x3f3f3f3f)
		printf("1\n%d\n",ans);
	else
	{
		int i;
		for(i=n;i>=1;i--)
		{
			int j;
			for(j=1;j<=m;j++)
				if(f[i][j]<0x3f3f3f3f)
					break;
			if(j<=m)
				break;
		}
		ans=0;
		for(int j=1;j<=i;j++)
			if(flag[j])
				ans++;
		printf("0\n%d\n",ans);
	}
	return 0;
}