\(一眼DP\)
相当于是在区间中选择若干段,各段总长度\(<=b\),然后求最大值。
首先考虑到区间\(DP\),然后发现复杂度\(O(n^6)\),要枚举长度,左端点,右端点,切割点,段数,左段段数,复杂度直接爆炸。
同时,空间复杂度\(O(n^3)\),也不可行(其实可以使用滚动数组。)
然后考虑:我为什么要考虑区间\(DP\) ?
原因是环。
于是就有了对于环的经典策略:
1.假装点1和点n断开,当一条链做
2.使点1和点强制连接
此时,已经枚举到了所有的可能情况。由于这是环形\(DP\),环上任意一点都可以作为起点,所以只需要破环成链,然后枚举接口处的所有情况就好了
于是,对于本题,考虑
1.点1与点n强制断开
2.点1与点n强制连接
然后就轻松的解出。
每天积累一个经典trick。