一道站外题的得到正解的过程

回复帖子

@北京 2021-05-04 23:04 回复

openjudge 8471 切割回文

这道题大佬们是怎么想到AC的思路的?

蒟蒻原先试了下线性dp,然后蒟蒻怎么也推不出状态转移方程,一点思路都没有;再试了一下区间dp,写完代码后提交发现n立方的时间复杂度直接tle……看完题解才知道只用n平方就够了(不愧是蒟蒻)

感觉dp好灵活……刷了二三十道黄题难度的dp发现黄题dp还是很多不会写,很想知道大佬们是怎么得到思路的

放点水:还有就是,不论是dp还是其他什么题,只要是绿题及以上难度的题蒟蒻不看题解就不会写了,就算看题解也还是很吃力……大佬们是什么时候可以轻松A过绿题的?什么时候可以轻松A过蓝题、紫题(乃至黑题)的?

感谢大佬指教

@Verdandi 2021-05-04 23:41 回复 举报

多做题,总结套路,锻炼思维就好了

虽然我现在仍然很菜/kk

@KnightL 2021-05-05 07:30 回复 举报

主要看考察的知识点吧。

比如我感觉同样是紫题树剖和 DP 难度就不一样。

@北京 2021-05-05 07:59 回复 举报

那么有木有大佬告诉我一下那道站外题是怎么得到思路的

@Verdandi 2021-05-05 08:29 回复 举报

只会 $O(n\Sigma)$做法/kk

具体就是建一个PAM,在上面跑dp,就像CF906E一样

@北京 2021-05-05 18:41 回复 举报

@钻剑君 我AC当然是依靠看题解啦

主要是没有看题解就AC的大佬们是怎么得到思路的

@北京 2021-05-05 18:46 回复 举报

@Verdandi 为什么这么复杂QAQ

CF906E黑题什么玩意儿……

至今没碰过黑题的蒟蒻表示害怕

@Verdandi 2021-05-05 18:54 回复 举报

啊,我会 $O(n^2)$了,我们可以 $O(n^2)$求出每个区间是不是回文串,然后定义 $f_{i,j}$为区间 $[i,j]$的答案,记忆化搜索就好了。

反馈
如果你认为某个帖子有问题,欢迎向洛谷反馈,以帮助更多的同学。



请具体说明理由,以增加反馈的可信度。