区间DP

动态规划题目灵活，状态定义形式多变，但还是有几种有一些讨论可以遵循的

比如有一类问题：

有 $n$ 堆石子，第 $i$ 堆有 $a_i$ 个，每次可以将相邻的两堆合并成一堆，然后能获得两堆石子数量之和的得分，直到合并成一整堆为止，问最大得分是多少？

这种问题的特征一般是：

1、中间状态属于连续一段区间。

2、可以将相邻的区间合并成一个区间。

该问题中，可以设 dp[l][r] 表示 a[l]~a[r] 的石子全部合并后得到的最大的分。

转移怎么做呢？

$$dp[l][r]=ma{x}_{k=l}^{r-1}(dp[l][k]+dp[k+1][r]+(a[l]\sim a[r]))$$

其中，$a[l]\sim a[r]$ 部分的求和可以用前缀和来实现 $O(1)$ 获得。

这其实是在枚举 $a[l]\sim a[r]$ 这一堆，最后一次合并的位置在哪里。

比如枚举到了 k ，那么就表示是先合并出 $a[l]a[k]$ 和 $a[k+1]a[r]$ 这两堆，再将这两堆合并成同一堆。

这就需要，对于所有的 $l\le k<r$，dp[l][k] 和 dp[k+1][r] 都是已知的。

所以我们的转移顺序应该是，按区间长度由小到大转移。

int n;cin>>n;
for(int i=1;i<=n;++i) cin>>a[i],s[i]=a[i]+s[i-1];
for(int len=2;len<=n;++len)
{
	for(int l=1,r=len;r<=n;++l,++r)//枚举所有长度为len的区间
    {
        for(int k=l;k<r;++k)//枚举这一堆最后一次合并的位置
        {
            dp[l][r]=max(dp[l][r],dp[l][k]+dp[k+1][r]+s[r]-s[l-1]);
        }
    }
}
cout<<dp[1][n]<<endl;

最后的答案位置是 dp[1][n]

可以预见，状态数是 $O(n^2)$ 的，转移是 $O(n)$ 的，所以总时间复杂度 $O(n^3)$ 。

环上问题

我们将第一次的问题升级，升级为所有石子围成一个环，其中 a[1] 和 a[n] 也相邻，其他条件不变。

采取的思路是破环成链，在序列的 a[n] 后面将序列再复制一次：

a[1],a[2],……,a[n],a[1],a[2],……a[n]

也就是对于大于 $n$ 的部分，$a[i]=a[i-n]$

因为这个环上必定有两个相邻节点之间是不进行合并的，我们可以看作这两个节点是这个序列的首和尾

然后仍然仿照上面的区间 $DP$ 进行转移，$len$ 只需要枚举到 $n$。

然后答案是所有长度为 $n$ 的区间里面的最大值。

即

for(int l=1,r=n;r<2*n;++l,++r) ans=max(ans,dp[l][r]);

练习题

P1880 [NOI1995] 石子合并

P1063 [NOIP2006 提高组] 能量项链

P3146 [USACO16OPEN] 248 G

P4170 [CQOI2007] 涂色

P1220 关路灯