题目分析

我们需要在给定的时间限制 $t$ 内，使用离散水平笔式绘图仪绘制尽可能多的线段。绘图仪的工作方式限制了笔的移动规则，使得绘制顺序和时间计算变得复杂。

解题思路

1. 线段排序：首先将所有线段按行号 $y$ 从小到大排序，同一行内的线段按结束坐标 $x_t$ 从小到大排序。这确保了绘图仪按从上到下、从左到右的顺序处理线段。

2. 动态规划（DP）：使用动态规划来计算绘制前 $i$ 个线段中的 $j$ 个线段所需的最短时间。定义 $dp[i][j]$ 为绘制前 $i$ 个线段中的 $j$ 个线段的最短时间。

3. 状态转移：

   • 初始化：绘制单个线段 $i$ 的时间为 $2 \times (x_t - x_s)$，即线段长度的两倍（因为绘制时移动时间加倍）。
   • 状态转移方程：对于每个线段 $i$ 和可能的绘制数量 $j$，遍历所有可能的 $k$（$k < i$），计算从绘制前 $k$ 个线段中的 $j-1$ 个线段到绘制线段 $i$ 的时间增量。时间增量包括从线段 $k$ 移动到线段 $i$ 的移动时间以及绘制线段 $i$ 的时间。

4. 结果提取：在填充 DP 表后，找到最大的 $j$ 使得存在某个 $i$ 满足 $dp[i][j] \leq t$。

关键公式

• 线段长度计算：绘制线段 $i$ 的时间为 $2 \times (a[i].ed - a[i].st)$。
• 移动时间计算：从线段 $k$ 移动到线段 $i$ 的时间为：
  • 如果 $a[k].y == a[i].y$，则时间为 $a[i].st - a[k].ed$（同一行内移动）。
  • 否则，时间为 $a[k].ed + a[i].st$（跨行移动，需返回最左侧）。

解决代码

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;

const int MAXN = 1010;

struct Node {
	int y, st, ed;
	void read() {
		scanf("%d%d%d", &y, &st, &ed);
	}
	bool operator < (const Node &rhs) const {
		if(y != rhs.y) return y < rhs.y;
		return ed < rhs.ed;
	}
};

int length(const Node &a, const Node &b) {
	if(a.y == b.y) return b.st - a.ed;
	return a.ed + b.st;
}

Node a[MAXN];
int dp[MAXN][MAXN];
int n, t, ans;

void solve() {
	memset(dp, 0x3f, sizeof(dp));
	ans = 0;
	for(int i = 1; i <= n; ++i) {
		if((dp[i][1] = 2 * a[i].ed - a[i].st) <= t) ans = max(ans, 1);
		for(int j = 2; j <= i; ++j) {
			for(int k = j - 1; k < i; ++k)
				dp[i][j] = min(dp[i][j], dp[k][j - 1] + length(a[k], a[i]));
			dp[i][j] += 2 * (a[i].ed - a[i].st);
			if(dp[i][j] <= t) ans = max(ans, j);
		}
	}
}

int main() {
	while(scanf("%d%d", &n, &t) != EOF && n + t) {
		for(int i = 1; i <= n; ++i) a[i].read();
		sort(a + 1, a + n + 1);
		solve();
		printf("%d\n", ans);
	}
}