【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]即可。

下面是代码:

 

stdKonjac

stdKonjac

一只挣扎的蒟蒻ACMer

评论太激烈有些评论需要亲动动手指翻页

留下你的评论

*评论支持代码高亮<pre class="prettyprint linenums">代码</pre>

*