环形结构上的动态规划问题

在许多环形结构问题中，我们都能通过枚举法，选择一个位置把环断开，变成线性结构进行计算，最后根据每次枚举的结果求出答案。我们把能用上述枚举方式求解的环形问题称为“可拆解的环形问题”，这也是本节的主要研究对象。我们的目标是采取适当策略避免枚举，从而降低时间复杂度。

通常来说，我们解决环形问题的方式有两种：

• 执行两次DP

• 破环为链

下面我们将结合例题分别介绍这两种方法

执行两次DP

\(\Large \text {例题:}\) \(\Large \text{P6064 Naptime G}\)

先来考虑一个“简化版”：假设第 \(N\) 个小时与次日第一个小时不是相连的，那么这就是一个明显的DP题：

用 \(dp_{i,j,0/1}\) 来表示在第 \(i\) 个小时，已经休息了 \(j\) 个小时，0 表示这个小时没在休息，1 表示这个小时正在休息。

状态转移方程就是：

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]);

初值：\(dp_{1,1,1}=0\)，\(dp_{1,0,0}=0\) 其余为 -INF。

答案：\(\max(dp_{n,b,0},dp_{n,b,1})\)。

但问题是第 \(N\) 个小时与次日第一个小时是相连的，上面的方法不能直接用。既然这样，那就再来一次强制连接：

强制让第 \(N\) 个小时睡觉，让次日第一个小时熟睡。

状态转移方程如上。

初值：\(dp_{1,1,1}=u_{1}\)，\(dp_{1,0,0}=0\)，其余为-INF。

答案：\(dp_{n,b,1}\)

具体来说，我们可以先将第 \(N\) 个小时与次日第一个小时断开，然后用上面的“简化版”的方法来得到一个答案。再强制让第 \(N\) 个小时睡觉，让次日第一个小时熟睡，用上面讨论的强制连接的方法得到第二个答案，两者取最大值即可。

ps：此题可用滚动数组优化空间

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,b,ans=0;
int f[2][3835][2],u[3835];
signed main(){
	cin>>n>>b;
	memset(f,-0x3f,sizeof(f));
	f[1][0][0]=f[1][1][1]=0;
	for(int i=1;i<=n;i++) cin>>u[i];
	for(int i=2;i<=n;i++){
		f[i&1][0][0]=0;
		for(int j=1;j<=i;j++){
			f[i&1][j][0]=max(f[(i-1)&1][j][0],f[(i-1)&1][j][1]);
			f[i&1][j][1]=max(f[(i-1)&1][j-1][0],f[(i-1)&1][j-1][1]+u[i]);
		}
	}
	ans=max(f[n&1][b][0],f[n&1][b][1]);
	memset(f,-0x3f,sizeof(f));
	f[1][1][1]=u[1];f[1][0][0]=0;
	for(int i=2;i<=n;i++){
		f[i&1][0][0]=0;
		for(int j=1;j<=i;j++){
			f[i&1][j][0]=max(f[(i-1)&1][j][0],f[(i-1)&1][j][1]);
			f[i&1][j][1]=max(f[(i-1)&1][j-1][0],f[(i-1)&1][j-1][1]+u[i]);
		}
	}
	ans=max(ans,f[n&1][b][1]);
	cout<<ans;
	return 0;
}

破环为链

\(\Large \text {例题:}\) \(\Large \text{环路运输}\)

题目描述

环上有 \(N\) 个点，每个点有点权 \(A_i\)，相邻仓库距离为 1，任意两点 \(i,j\) 之间的距离定义为沿环的两侧分别从 \(i\) 前往 \(j\) 的距离中的较小值，即 \(dis_{i,j}=min(|i-j|,N-|i-j|)\)。定义任意两点 \(i,j\) 之间运输货物的代价为 \(A_i+A_j+dis_{i,j}\)，求在环上哪两点间运输货物的代价最大。\(1 \le N \le 10^6\)。

解法

断环为链的思想可以简述为：对于一个长度为 \(N\) 的环，我们不妨将其断开并延长一倍，使之变成一条长度为 \(2N\) 的链，并将其划分为若干部分分别考虑。

我们在任意位置（例如仓库 \(1\) 和 \(N\) 之间）把环断开，复制一倍接在末尾，形成长
度为 \(2N\) 的直线公路。在转化之后的模型中，公路旁均匀分布着 \(2N\) 座仓库，其中 \(A_i=A_{i+N}(1 \le i \le N)\)。

对于原来环形公路上的任意两座仓库 \(i\) 和 \(j\) \((1 \le j<i \le N)\)，如果 \(i-j \le N/2\)，那么在新的直线公路上，仍然可以对应成在 \(i\) 和 \(j\) 之间运送货物，代价为\(A_i+A_j+i-j\) 。

如果 \(i-j>N/2\)，那么可以对应成在 \(i\) 和 \(j+N\) 之间运送货物，代价为 \(A_i+ A_{j+N}+j+N-i\)，其中 \(j+N-i=N-(i-j) \le N/2\)。

综上所述，原问题可以等价转化为：长度为 \(2N\) 的直线公路上，在满足 \(1 \le j<i \le 2N\) 并且 \(i-j \le N/2\) 的哪两座仓库 \(i\) 和 \(j\) 之间运送货物，运送代价\(A_i+A_j+i-j\)最大?

我们可以枚举 \(i\)，对于每个 \(i\)，需要找到一个 \(j \in [i-N/2,i-1]\)，使 \(A_j-j\) 尽量大。在“最大子序和”这道例题的解答中，我们已经探讨过同样的问题。使用单调队列进行维护，可以在均摊 \(O(1)\) 的时间内找到这样的 \(j\)。整个算法的时间复杂度为 \(O(N)\)。

#include <bits/stdc++.h>

using namespace std;
int n,ans;
int a[2000002]; 
deque<int> q;
int main() {
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		a[i+n]=a[i];
	}
	q.push_back(1);
	for(int i=2;i<=2*n;i++){
		while(q.size()&&i-q.front()>n/2){
			q.pop_front();
		}
		int j=q.front();
		ans=max(ans,a[i]+i+a[j]-j);
		while(q.size()&&a[q.back()]-q.back()<=a[i]-i){
			q.pop_back();
		}
		q.push_back(i);
	}
	cout<<ans;
	return 0;
}

有后效性的状态转移方程

从最初学习DP开始，我们就多次强调，“阶段”是动态规划的三要素之一，“无后效性”是应用动态规划算法的三前提之一。事实上，在一些题目中，当我们根据题目的关键点抽象出“状态维度”，并设计出状态表示和状态转移方程后，却发现这道形似DP的题目不满足“无后效性”这一基本条件——部分状态之间互相转移、互相影响，构成了环形，无法确定出一个合适的DP“阶段”，从而沿着某个方向执行递推。

事实上，我们可以把动态规划的各状态看作未知量，状态的转移看作若干个方程。如果仅仅是“无后效性”这一条前提不能满足，并且状态转移方程都是一次方程，那么我们可以 不进行线性递推，而是用高斯消元直接求出状态转移方程的解。

在更多的题目中，动态规划的状态转移“分阶段带环”——我们需要把DP和高斯消元相结合，在整体层面采用动态规划框架，而在局部使用高斯消元解出互相影响的状态。我们用一道例题来具体说明这类情况。