算法简介：占理不饶人

环形动态规划，是我们做动归过程中极其常见的一种类型。它的推导过程有时候非常循规蹈矩，或者说存在一些特定的思路来搞定，正巧遇到了新的一种做法，于是写了这篇文章讲一下。

我们都知道，环形动态规划的特点，就是维护结构是一个环。环的特殊之处就是相对于线性结构，就是数组这类来说，数组只会影响前一个或者后一个，如果在开头或者结尾就溢出之类的。

但是如果是环状结构，就会发现他们的特殊处在于最后一个会影响第一个，第一个会影响最后一个，这样的存在让我们非常难受，于是乎，就会有下面几种特殊的方式来转化环状结构。

算法演示：最终解释权

那么说到转化环结构，常见的有两个方式。

  1. 第一个，暴力点，常见的破环为链
  2. 第二个，斯文点，罕见的分讨结果

但是他们的相同之处在于都是运用一种转化来使环变为线性结构的形式，只不过表现形式不同而已。我们下面可以用两个例题来大致认识一下这两种方法。

算法例一：真火炼宝印

直接上题！

题目大意

在一个圆形操场的四周摆放 $N$ 堆石子，现要将石子有次序地合并成一堆，规定每次只能选相邻的 $2$ 堆合并成新的一堆，并将新的一堆的石子数，记为该次合并的得分。

试设计出一个算法,计算出将 $N$ 堆石子合并成 $1$ 堆的最小得分和最大得分。

$1\leq N\leq 100$，$0\leq a_i\leq 20$。

题目思路

典型的环形动态规划。我们发现，这样的环形DP，它只需要两两合并，似乎没有什么特殊条件。于是呢，我们就可以略略变通一波，退而求其次，如果是一个链，如何解决？

显然的区间DP，因为 这就是一眼区间DP啊有什么问题吗 我们发现它存在性质，两两合并的顺序一定可以用区间DP的合并顺序来模拟，这就是显而易见的了。

但是问题就是怎么做这个所谓的区间DP呢？我们总不能大力在环上找两个端点然后判断他们分别是左还是右来统计答案吧，码量 promax ！暴政！

这时候，破环为链的技巧脱颖而出，由于这种类型的 DP 没有什么特殊的限制，就是是说合并是你想合就合，没有说你选了那个要什么什么后果，就是字面意思的合成即有价值。这时候破环为链就可以用了。

所谓破环为链，就是把一个环写两遍，变成一个长度为 $2\times n$ 的链。这时候对于任意的 $1\le i\le n$ ，一定存在一个区间 $[i,i+n-1]$ 是这个环的一种排列，最终的答案就是如此，处理完以后，求出所有 $[i,i+n-1]$ 的最大值。

题目代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
// Copied from Solution
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
using namespace std;
const int MAXN=0xfffff,MINN=0;
inline int read()//快读
{
    int x=0,w=0;
    char ch=0;
    while(!isdigit(ch))
    {
        w|=ch=='-',ch=getchar();
    }
    while(isdigit(ch))
    {
        x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
    }
    return w?-x:x;
}
int T[210],F1[210][210],F2[210][210],sum[210];//T为输入的石子堆，F1为第一问的答案求解，F2为第二问的答案求解，sum为求前ｉ堆石子的合总值
int main(void)
{
    int N=read();
    for(int i=1; i<=N; ++i) T[i]=read(),T[i+N]=T[i];／／变环为链
    for(int i=1; i<=2*N; ++i) sum[i]=sum[i-1]+T[i],F1[i][i]=0,F2[i][i]=0;//注意要把Ｆ［ｉ］［ｉ］＝０
    for(int L=2; L<=N; ++L)
    {
        for(int i=1; i<=2*N-L+1; ++i)
        {
            int j=i+L-1;
            F1[i][j]=MAXN,F2[i][j]=MINN;//初始化
            for(int k=i; k<j; ++k)
            {

                F1[i][j]=min(F1[i][k]+F1[k+1][j],F1[i][j]);//寻找最小值
                F2[i][j]=max(F2[i][k]+F2[k+1][j],F2[i][j]);//寻找最大值
            }
            F1[i][j]+=(sum[j]-sum[i-1]);//加上此次合并值
            F2[i][j]+=(sum[j]-sum[i-1]);
        }
    }
    int ANS1=MAXN,ANS2=MINN;
    for(int i=1; i<=N; ++i)
    {
        ANS1=min(ANS1,F1[i][i+N-1]);//求解答案１
        ANS2=max(ANS2,F2[i][i+N-1]);//求解答案２
    }
    printf("%d\n%d",ANS1,ANS2);//输出
    return 0;
}

算法例二：丹书金铁券

再次闪击！

题目大意

贝茜是一只非常缺觉的奶牛．她的一天被平均分割成 $N$ 段（$3 \leq N \leq 3830$），但是她要用其中的 $B$ 段时间（$2 \leq B \lt N$）睡觉。每段时间都有一个效用值 $U_i$（$0 \leq U_i \leq 2 \times 10^5$），只有当她睡觉的时候，才会发挥效用。

有了闹钟的帮助，贝茜可以选择任意的时间入睡，当然，她只能在时间划分的边界处入睡、醒来。

贝茜想使所有睡觉效用的总和最大。不幸的是，每一段睡眠的第一个时间阶段都是“入睡”阶段，而旦不记入效用值。

时间阶段是不断循环的圆（一天一天是循环的嘛），假如贝茜在时间 $N$ 和时间 $1$ 睡觉，那么她将得到时间 $1$ 的效用值。

题目思路

OK 啊，和上一题不同的是，这道题扑面而来的就是一种高端的气息。简单来说，就是就是就是就是，和上一题差距十年的压迫感。 回归正题，可以观察一下这道题的性质，同样是环，于是我们先不考虑如何破环为链，而是优先考虑如何在数据为链的情况下通过这道题。

如果我们设置状态 $dp[i][j][0/1]$ 表示在前 $i$ 个小时中，睡了 $j$ 小时觉，当前正在（1）不在（0）睡觉的状态。然后轻而易举的得出转移方程：

第一个表达式没什么好说的了吧，主要是第二个，为什么 min 的第一项不用加上当前的休息效用？因为题目中明确说过，这属于 “入睡阶段” 不算入总休息效用。

似乎挺顺利的，难道就这么结束了？仔细看看，这时候就凸现出了一个问题，我们这时候是肯定了第一个时间段和最后一个时间段的不相关，也就是说这时候答案是不正确的。这就是这道题不可以用所谓 破环为链 技巧的原因。那么不能破环为链我们怎么办？

显然的，他只是规定了不相关，也就是说我们存在 相关 和 不相关 两种可能，不相关很简单，按照上面的正常递推。但是如果是相关，我们就要强制第一个和最后一个连接，也就是第一个要强制附上权值 $u[1]$ 并且最后一个时间段的状态只能是 $dp[n][n][1]$ 也就是正在休息。

这种通过强制控制两端状态，进行两次甚至多次动态规划的算法，叫做 分讨结果 这个名字当然是我自己乱取的，网上一般叫做 二次动规法

题目代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
// Coiped from Solution
#include<bits/stdc++.h>
using namespace std;
int dp[3831][3831][2],n,b,u[3831],ans;
int main() {
	scanf("%d%d",&n,&b);
	for(int i=1;i<=n;i++)scanf("%d",u+i);
	memset(dp,-0x3f,sizeof(dp));
	dp[1][1][1]=dp[1][0][0]=0;
	for(int i=2;i<=n;i++){
		dp[i][0][0]=dp[i-1][0][0];
		for(int j=1;j<=b;j++){
			dp[i][j][0]=max(dp[i-1][j][0],dp[i-1][j][1]);
			dp[i][j][1]=max(dp[i-1][j-1][0],dp[i-1][j-1][1]+u[i]);
		}
	}
	ans=max(dp[n][b][0],dp[n][b][1]);
	memset(dp,-0x3f,sizeof(dp));
	dp[1][1][1]=u[1];
	dp[1][0][0]=0;
	for(int i=2;i<=n;i++){
		dp[i][0][0]=dp[i-1][0][0];
		for(int j=1;j<=b;j++){
			dp[i][j][0]=max(dp[i-1][j][0],dp[i-1][j][1]);
			dp[i][j][1]=max(dp[i-1][j-1][0],dp[i-1][j-1][1]+u[i]);
		}
	}
	ans=max(ans,dp[n][b][1]);
	printf("%d\n",ans);
	return 0;
}

算法提示：遵法切结书

那么说了这么多，我们大概的总结一下两个算法的相同点以及不同点，还有注意事项。

首先对于环形 DP 的特点：转化环结构，便于求解。

其次是两种方式的不同点：对于破环为链来说，不要求有联系。对于二次动规来说，需要分类讨论开始和结尾的状态，这时候不可以破环为链。

对于两种方法格子有注意事项：

  1. 破环为链内存开两倍！
  2. 小心访问非法内存！比如说访问了 $dp[-1]$ 等等等等

必要的存在流程：

  1. 优先考虑链结构做法
  2. 思考如何破环
  3. 呈现最终结果

算法总结：是额外条款

请查看相关算法标签喵！

参考资料（以下排名不分先后）