题解

思路概述

• 把横坐标视为时间轴，设 dp[i][h] 表示到达第 i 根柱子（横坐标 i）且当前高度为 h（1…m）所需的最少点击次数。每一列给出“上升高度 X”“下降高度 Y”，因此从上一列转移只有两种操作：点击让高度增加 X，或者不点让高度减少 Y。
• 为了避免爆表，数组中还需要维护高度超过 m 的情况：当连按多次使高度超过 m 时表示失败，所以高度循环限制在 0..m，并用 INF 标记不可达。
• 当遇到管道时，直接把不在合法区间 [L,H) 的状态设为 INF；如果全列变成 INF，说明无法通过的最早管道就是当前这根，输出失败以及已通过的数量。
• 由于每一列的状态仅依赖上一列，可使用滚动数组 dp[i&1] 节省空间；同时额外处理“高度超过 m”的滚出状态，把落入 m 的转移取最小值。

正确性说明

• 状态转移只包含“从上一列点击/不点转移过来”的方案，正好覆盖题意的所有控制策略，且每个状态记录最少点击次数，因此最终答案即通过 DP 得到的最小值。
• 管道过滤逻辑保证了任何落在缝隙之外的状态被淘汰；一旦某列全部不可达，就说明此时已经无法继续，管道编号正是题目所求。

复杂度

状态数量 O(n*m)，每次转移和管道过滤为线性处理，总复杂度 O(n*m)，空间 O(m)。

#include <bits/stdc++.h>
using namespace std;
const long long INF = 0x3f3f3f3f3f3f3f3f;
int x[10005], y[10005];
long long dp[2][2005];
struct node
{
	int p, l, h;
}a[10005];
bool cmp(node a, node b)
{
	return a.p < b.p;
}
signed main()
{
	int n, m, k, cnt = 1;
	long long ans;
	cin >> n >> m >> k;
	for (int i = 1; i <= n; i++)
		cin >> x[i] >> y[i];
	for (int i = 1; i <= k; i++)
		cin >> a[i].p >> a[i].l >> a[i].h;
	sort(a + 1, a + 1 + k, cmp);
	for (int i = 0; i <= m; i++)
		dp[0][i] = 0;
	for (int i = 1; i <= n; i++)
		dp[i & 1][0] = INF;
	for (int i = 1; i <= n; i++)
	{
		for (int j = 0; j <= m; j++)
			dp[i & 1][j] = INF;
		for (int j = x[i] + 1; j <= x[i] + m; j++)
			dp[i & 1][j] = min(dp[i & 1][j - x[i]], dp[i & 1 ^ 1][j - x[i]]) + 1;
		for (int j = m + 1; j <= x[i] + m; j++)
			dp[i & 1][m] = min(dp[i & 1][m], dp[i & 1][j]);
		for (int j = 1; j <= m - y[i]; j++)
			dp[i & 1][j] = min(dp[i & 1][j], dp[i & 1 ^ 1][j + y[i]]);
		if (i == a[cnt].p)
		{
			for (int j = 0; j <= a[cnt].l; j++)
				dp[i & 1][j] = INF;
			for (int j = a[cnt].h; j <= m; j++)
				dp[i & 1][j] = INF;
			ans = INF;
			for (int j = 1; j <= m; j++)
				ans = min(ans, dp[i & 1][j]);
			if (ans == INF)
			{
				cout << "0\n" << cnt - 1;
				return 0;
			}
			cnt++;
		}
	}
	ans = INF;
	for (int j = 1; j <= m; j++)
		ans = min(ans, dp[n & 1][j]);
	cout << "1\n" << ans;
	return 0;
}