【bj】模拟赛 7/16

A：CF425E Sereja and Sets

• 题意；

给定 \(n\) 个点，其中有 \(m\) 个区间，满足任意两点形成的区间被包含其中，端点可重合（所以其实 \(m\) 是个定值），一个区间集合合法，当且仅当从这个区间选出的最多的不重合区间的数量为 \(k\)，问你有多少种合法的选择方案。

输入格式

输入仅一行，\(n,k\)。\((1\le n\le 500,\ \ 0\le k\le 500)\)。

输出格式

输出一行一个正整数，表示答案。对 \(10^9+7\) 取模。

• 思路：

这题能做，但介于某人是个数数题渣渣，看到就直接跳了qwq

这题我们先考虑一下，当给定一个区间集合，它能选出的最多的不重合区间为多少。

这是个很经典的问题，可以直接将所有区间按右端点排序后贪心去选。

然后看回原题，原题要我们算方案数，那么可以 dp。

状态为 \(f_{i,j}\) 表示前 \(i\) 个点，当前选择的区间的右端点为 \(i\)，前一个区间右端点为 \(j\) 时的合法方案数。

首先考虑到方案合法的那个贪心首先我们最后这个区间的左端点必须 \(>j\)，然后注意到一个合法方案中，有些区间它可能不在最终的最多选择中，但是它是在原始区间集合中的，只是没选它罢了。

那么这些东西我们不能落，所以得乘上一个系数，具体而言看具体而言。