题目描述：
给出一个长度为L的木板，上面贴着N张海报，每张海报有一个起点和一个终点，表示海报覆盖的区间。现在要从木板上撕下K张海报，使得剩下的海报中，任意两张之间都没有重叠的部分（即它们覆盖的区间互不相交）。问有多少种撕下海报的方法。
输入：
- 第一行包含一个整数T，表示测试数据的组数。
- 每组测试数据的第一行包含两个整数N和K，分别表示海报的数量和需要撕下的海报数量。
- 接下来N行，每行包含两个整数Ai和Bi（Ai < Bi），表示第i张海报覆盖的区间。
输出：
- 对于每组测试数据，输出一行，包含一个整数，表示撕下海报的方法数。
解题思路：
- 区间排序：首先将所有海报按照区间的起点进行排序，如果起点相同，则按照终点进行排序。
-
动态规划：使用动态规划来解决这个问题。定义
dp[i][j]表示前i张海报中撕下j张后，剩余海报区间不重叠的方案数。 -
状态转移：
- 如果不撕下第i张海报，那么
dp[i][j]应该加上dp[i-1][j]的值。 - 如果撕下第i张海报，需要找到最后一张与第i张海报不重叠的海报位置
p，那么dp[i][j]应该加上dp[p][j-1]的值。
- 如果不撕下第i张海报，那么
- 二分查找：为了高效地找到与第i张海报不重叠的最后一张海报的位置，可以使用二分查找。
具体实现：
#include
struct Poster { int start, end; bool operator < (const Poster& other) const { if (start != other.start) return start < other.start; return end < other.end; } };
int main() {
int T;
cin >> T;
while (T--) {
int N, K;
cin >> N >> K;
vector
vector> dp(N + 1, vector(K + 1, 0));
dp[0][0] = 1; // 没有海报时，撕下0张的方法数为1
for (int i = 1; i <= N; ++i) {
for (int j = 0; j <= K; ++j) {
dp[i][j] = dp[i - 1][j]; // 不撕下第i张海报
if (j > 0) {
// 二分查找最后一个不与第i张海报重叠的海报
int left = 0, right = i - 1;
while (left < right) {
int mid = (left + right + 1) / 2;
if (posters[mid - 1].end < posters[i - 1].start) {
left = mid;
} else {
right = mid - 1;
}
}
if (posters[left - 1].end < posters[i - 1].start) {
dp[i][j] += dp[left][j - 1];
}
}
}
}
cout << dp[N][K] << endl;
}
return 0; }
解释：
- 结构体 Poster：用于存储海报的起点和终点，并重载
<运算符以便排序。 - 输入处理：读取测试数据的组数T，对于每组数据读取N和K，以及每张海报的起点和终点。
- 排序：将海报按照起点和终点进行排序。
- 动态规划数组 dp：
dp[i][j]表示前i张海报中撕下j张后，剩余海报区间不重叠的方案数。 - 状态转移：通过不撕下当前海报和撕下当前海报两种情况来更新dp数组。
- 二分查找：用于高效地找到最后一个不与当前海报重叠的海报位置。
通过上述步骤，可以高效地求解出每组测试数据的答案。
发表回复