2025牛客暑期多校训练营1——Problem I. 铁棒切割（状态转移，区间dp，排序）

思路讲解

那么，我们发现这道题目的难点在于怎么让这个不平衡度单调下降的同时，让这个切割代价最小。

那么，我个人认为，这个不平衡度的单调下降不难，因为这个是只和前一个状态有关系，转移的时候校验一下就行。

现在的难点就是在于这个状态定义。

然后我看了一下，其实我想的没什么太大问题，就是把这个第几次砍给干掉就行。状态定义就是 $dp[l][r]$ 。

不难发现，其会形成类似于区间树的样子。

然后难点就来到了状态转移。

如果不用考虑不平衡度的单调下降，那么这个状态转移就简单了，就是 P1880 [NOI1995] 石子合并。但是显然没有说那么简单。

1
2
3

// 如果我们解决不了到底谁更优，是较大的imbalance，还是较小的代价
// 那么我们可以都存下来
V<V<V<pll>>> dp(N+5,V<V<pll>>(N+5));

源代码