D - 渣渣仰慕的爱丽丝 HDU - 6249(背包问题变形)
爱丽丝喜欢集邮。她现在在邮局买一些新邮票。
世界上有各种各样的邮票;它们的编号是1到N。但是,邮票不是单独出售的;必须成套购买。有M套不同的邮票可供选择;
第i套包括编号从li到ri的邮票 。同一枚邮票可能会出现在不止一套邮票中,而且可能在任何一套邮票中都找不到一枚或多枚邮票。
所有套装的价格都是一样的;因为爱丽丝的预算有限,她最多只能买K套不同的邮票。爱丽丝最多能买到多少种不同的邮票? Input
输入从一行开始,其中包含一个整数T,即测试用例的数量。接下来是T测试用例。
每个测试用例都以一行开始,其中包含三个整数:N、M和K:可用的不同类型邮票的数量、可用邮票集的数量,以及Alice可以购买的最大邮票集数量。
这些行中的第i行表示第i个套邮票,包含两个整数li和ri,表示该套邮票中可用邮票数目的范围。 1≤T≤100 1≤K≤M
1≤N,M≤2000 1≤Li≤Ri≤N Output 对于每个测试用例,输出一行包含“case #x:
y”,其中x是测试用例号(从1开始),y是Alice可以得到的不同类型邮票的最大数量。
Sample Input
2
5 3 2
3 4
1 1
1 3
100 2 1
1 50
90 100
Sample Output
Case #1: 4
Case #2: 50
思路
链接
最新文章
热门文章