[问题] 最大平面弦集合的问题 shiauyeu PTT批踢踢实业坊

[问题] 最大平面弦集合的问题

楼主: shiauyeu (呵呵呵呵呵呵呵呵) 2021-11-28 21:08:07

最近在解一个DP的问题
如上图这题的最大平面弦集合个数是3 分别是0 4、5 7、8 11
因为我用DP写出来的在喂5000条下跑得有够慢
所以我换了一种写法
我先把输入的弦两端相减求长度
比方说0 4相减是4，1 9相减是8 然后把所有长度做排序
排序完后以这题来说会是
5 7
8 11
0 4
2 6
3 10
1 9
接着把5 7包著的弦(6这条)删掉
8 11包著的弦(9和10两条)删掉
依此类推
最后出来的结果会是5 7、8 11、0 4
但是在喂500条执行出来的结果是错的想上来问问大家我想不出来这个方法为什么不行
谢谢!!

作者: wtchen (没有存在感的人) 2021-11-28 21:16:00

程式码呢？

作者: gogogofuxk (小炫) 2021-11-28 22:55:00

看内文像是从短做到长？反例：(0,10),(8,13),(12,30)btw 这感觉应该是interval scheduling的变形

作者: lc85301 (pomelocandy) 2021-11-29 10:47:00

听你的描述，你是用了那个吧

作者: simon860730 (╰电磁学╮╭爆炸囉╯) 2021-11-29 11:23:00

看来楼上跟我理解差不多他应该是用了那个没错

作者: a28503662 (Ok Rocker) 2021-11-29 16:36:00

你应该跟我同班吧作业自己写==翻了一下是学弟而且还发过心得文帮你补推==

楼主: shiauyeu (呵呵呵呵呵呵呵呵) 2021-11-30 01:20:00

那个是哪个XD 后来我想了一下如同二楼举的反例确实有BUG 还是乖乖用DP 但是我写的DP光500条就要跑10秒左右XD

作者: f953024 (=.=a) 2021-11-30 02:40:00

老实说你最大的问题就是用了那个吧

作者: lc85301 (pomelocandy) 2021-11-30 22:43:00

这位先生叫武雄是吧

作者: ChineseKing (安安) 2021-12-19 13:48:00

你有没有想过你到底真正在追求什么呢?

作者: alan23273850 2021-12-28 19:11:00

先问什么叫做最大平面弦集合

继续阅读

[问题][QT] windeploy 之后程式逻辑出错liu2007 [问题] 后输入运算式，堆叠后归零justgetup [问题] LFU实作问题ars0921 Re: [问题] QT Sqlite语法以及全文检索FTS问题pinefruit [问题] QT Sqlite语法以及全文检索FTS问题liu2007 [问题] 新手请问opencv读取Vvvahc Re: [问题] auto用法一问dzwei [问题] 矩阵相乘irpolo1 [问题] 请问ffmpeg如何build msvc不做optimize?Keitaro [问题] C语言初学观念请益how0919