stdKonjac's Blog

An AC a day keeps the WA away ~

【Segment Erasing】

【数据描述】

Bob在数轴上随手画了N条线段,但是有线段之间有重合,这样很不和谐。于是他想擦去一些线段,使得剩余的线段无重合。他很容易就知道了最少需要擦去多少线段,现在他感兴趣的是擦去最少线段有多少种方法?

【输入格式】

第一行:N<=1000

接下来N行,每行两个整数 (整数<=5000)表示一条线段的两个端点。

(注意:所谓的线段均为开区间,即(3,6)与(6,9)不重合)。

【输出格式】

仅一行,两个数,即最少需要擦去的线段和擦的方法数。

保证答案不超过2^64

【输入样例】

5

1 3

3 5

4 6

8 9

4 6

【输出格式】

2 3

【数据说明】

20%:N<=20

50%:N<=100

100%:N<=1000

令F[i]表示当前选到第i条线段(一定选i)的最优解,G[i]表示到i为止擦最少线段的方案数,那么若有F[j]+1>F[i],则更新F[i],同时更新G[i]。若有F[j]+1=F[i]那么把G[j]累加进G[i]即可。

下面是代码:

 

点赞

发表评论

电子邮件地址不会被公开。 必填项已用*标注

*

This site uses Akismet to reduce spam. Learn how your comment data is processed.