【做题笔记】P6064 && SP283

发布时间 2023-07-09 17:04:18作者: Aslf_Ek

\(一眼DP\)

相当于是在区间中选择若干段,各段总长度\(<=b\),然后求最大值。

首先考虑到区间\(DP\),然后发现复杂度\(O(n^6)\),要枚举长度,左端点,右端点,切割点,段数,左段段数,复杂度直接爆炸。

同时,空间复杂度\(O(n^3)\),也不可行(其实可以使用滚动数组。)

然后考虑:我为什么要考虑区间\(DP\)

原因是

于是就有了对于环的经典策略:

1.假装点1和点n断开,当一条链做

2.使点1和点强制连接

此时,已经枚举到了所有的可能情况。由于这是环形\(DP\)环上任意一点都可以作为起点,所以只需要破环成链,然后枚举接口处的所有情况就好了

于是,对于本题,考虑

1.点1与点n强制断开
2.点1与点n强制连接

然后就轻松的解出。

每天积累一个经典trick。