环形区间dp

dp是OI路上的一道天堑，很明显俺还在这个坑里

1. 定义

 这一类问题最典型的就是合并石子问题，即在一个区间上，进行元素的合并，将相邻小的元素或者区间逐渐合并成一个大的区间，最终合并为一个大的区间，在这个过程，我们需要使得一些量取得最大值，这大概就是区间dp的定义

2. 例题

NOI1995合并石子

3. 思路

1.求石子合并的最大值，转移方程如下

f[i][j] = max(f[i][k]+f[k+1][j]) + sum[i][j]

2.求石子合并的最小值，转移方程如下

f[i][j] = min(f[i][k]+f[k+1][j]) + sum[i][j]

关键的点在于进行区间中间点的选取，每次选取一个合适的k值进行dp，得到这个区间内的最终值，可以说是很经典的一道题了。

对于环形的处理我们可以选择取对最后一个点进行特判，也可以选择开两倍的空间。

for(int len = 1;len < n;len++)for(int i = 1,j = i+len;(j < 2*n)&&(i < 2*n);i++,j++)for(int k = i;k < j;k++)dp[i][j] = max(dp[i][j], dp[i][k] + dp[k+1][j] + sum(i,j));
for(int i = 1;i <= n;i++)ans = max(ans, dp[i][i+n-1]);

 上面大概就是主要循环的全部内容，我们先枚举区间的长度，从$1\to n-1$，再枚举我们的起点，同时保证我们的起点和终点都在2*n的范围内,最终得到在 $n-1$ 长度的区间内的最大解。最小值的解法也类似，$max\to min$即可

4 基于合并石子的变种

NOIP2006 能量项链

这道题的基本意思和上面一个是一样的，只不过这次使用的相乘，本质还是一样的

对于这道题，我们可以得到的状态转移方程

f[i][j] = max(f[i][k] + f[k+1][j] + num[i]*num[j]*num[k]);

于是我们按照上面的思路去写

for(int len = 1;len < n;len++)for(int i = 1,j = 1+len;j <= (2*n);i++,j++)for(int k = i+1;k < j;k++)dp[i][j] = max(dp[i][j], dp[i][k] + dp[k+1][j] + num[i]*num[j]*num[k]);

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！