level 1
一个平面上有互相交叉的若干长短不一的线段，这其中肯定有若干互不交叉的线段组成的线段子集，请问如何求得互不交叉的线段总长最长的线段子集，或者换一个方式，如何拿掉总长最短的线段使得剩余线段互不交叉
2011年09月08日 09点09分
1
level 10
如果所有的线段长度都是1，弱化的问题等价于求线段集S的intersection graph的独立集。这个问题是npc的，也就是很可能没有多项式非近似算法
2011年09月08日 10点09分
2
level 1
咱不懂别随便说啊。。
不知道线段长度范围如何，但是动态规划就可以做了，先按右端点排个序，然后F[i]表示以第i条线段为结尾，线段总和最多是多长，然后从1~i-1更新答案即可。。
2011年09月08日 11点09分
3
level 10
那你告诉我转移方程是什么？你那方法明明是基于所有线段共线的
2011年09月08日 11点09分
4