解决环形DP问题，最暴力的方式是通过枚举选择每一个可以断开的位置，使之变成线性DP问题进行求解，再从每次枚举的结果中得出正确答案。但如此一来时时间复杂度就变得很高。

解决环形问题常用的策略如下：

两次DP：第一次在任意位置把环断开，按照线性问题进行求解。第二次通过适当的条件和赋值，保证计算出的状态等价于把断开的位置强制相连。两次合起来就能覆盖整个问题。

断环成链：在任意位置把环断开成链，然后复制一倍接在末尾。

Naptime

问题

一只母牛，一天被划分为时间相等的$N \;(3 \leq N \leq 3830)$ 个时期。 ，只有 $B\;(2\leq B < N)$ 个周期可以用来睡觉，每个周期有一个体力的恢复值 $U_i$ 。一天内的睡眠的时间可以分为连续的几段，但是在每段的第一个周期是用来准备入睡的，不能获得恢复的体力。请帮忙设计一个睡眠计划，使它能在一天内恢复的体力最多，输出该体力值。

分析

先不考虑第 $N$ 个周期和第1个周期连接的情况。

$F[i][j][1]$ 表示在这天的前 $i$ 个周期睡了 $j$ 个周期最多恢复的体力值。并且第 $i$ 个周期睡觉了。

$F[i][j][0]$ 表示在这天的前 $i$ 个周期睡了 $j$ 个周期最多恢复的体力值，并且第 $i$ 个周期没有睡觉。

则有转移方程
$$
F[i][j][1] = max(F[i-1][j-1][1] + U[i],\; F[i-1][j-1][0]); \\
F[i][j][0] = max(F[i-1][j][1], \;F[i-1][j][0]);
$$
初始：$F[1][1][1] = 0,\; F[1][0][0] = 0; $ 其余为 -INF。目标：$max(F[N][B][1], F[N][B][0])$

再考虑再考虑 再 $N$ 和1之间有循环时。此时要令第 $N$ 个小时处于休息状态。

此时有，初始：$F[1][1][1] = U[i];$ 其余为 -INF。目标：$F[N][B][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
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cstring>

using namespace std;

const int N = 3836;
#define INF (0x3f3f3f3f)

int n, b;
int u[N];
int f[2][N][2];

int main(int argc, const char * argv[]) {
    scanf("%d%d", &n, &b);
    for (int i = 1; i <= n; ++i) {
        scanf("%d", &u[i]);
    }
    if (b == 0)  { printf ("0"); exit (0); }
    memset(f, 0x80, sizeof(f));
    f[1 & 1][1][1] = 0;
    f[1][1][0] = -INF;
    f[1][0][1] = -INF;
    f[1 & 1][0][0] = 0;
    for (int i = 2; i <= n; ++i) {
        f[i&1][0][0] = 0;
        f[i&1][0][1] = -INF;
        for (int j = 1; j <= i && j <= b; ++j) {
            if (i-1>=j) f[i&1][j][0] = max(f[(i-1)&1][j][1], f[(i-1)&1][j][0]);
            if (j-1>=0) f[i&1][j][1] = max(f[(i-1)&1][j-1][1]+u[i], f[(i-1)&1][j-1][0]);
        }
    }

    int ans = max(f[n&1][b][1], f[n&1][b][0]);
    memset(f, 0x80, sizeof(f));
    f[1][1][1] = u[1];
    for (int i = 2; i <= n; ++i) {
        f[i&1][0][0] = 0;
        f[i&1][0][1] = -INF;
        for (int j = 1; j <= i && j <= b; ++j) {
            if (i-1>=j) f[i&1][j][0] = max(f[(i-1)&1][j][1], f[(i-1)&1][j][0]);
            if (j-1>=0) f[i&1][j][1] = max(f[(i-1)&1][j-1][1]+u[i], f[(i-1)&1][j-1][0]);
        }
    }
    ans = max(ans, f[n&1][b][1]);

    printf("%d\n", ans);

    return 0;
}

环路运输

问题

在一条环形公路旁均匀地分布着 $N$ 座仓库，编号为 1~N，编号为 $i$ 的仓库与编号为 $j$ 的仓库之间的距离定义为 $dist(i,j)=min⁡(|i-j|,N-|i-j|)$，也就是逆时针或顺时针从 $i$ 到 $j$ 中较近的一种。每座仓库都存有货物，其中编号为 $i$ 的仓库库存量为 $A_i$。在 $i$ 和 $j$ 两座仓库之间运送货物需要的代价为 $A_i+A_j+dist(i,j)$。求在哪两座仓库之间运送货物需要的代价最大。输出最大代价。

分析

在 $N$ 和 1 之间为位置将环形公路剪开，然后在复制相同的一段在其末尾，使得有 $2N$ 的仓库散落在直线公路的两旁，同时有 $A_i = A_{i+n}$。假设有 $1 \leq j < i \leq N$，若 $i-j \leq n/2$ 则 $dist(i, j) = i-j$；若 $i-j > n/2$ 则 $dist(i, j) = j+n-i = n-(i-j) \leq n/2$。

观察可知，所有的所有 $dis(i, j) \leq n/2$，因此可以枚举$\forall i\in[1, 2N]$，寻找 $\min \limits_{j\in[i-n/2,\; i-1]}{A_j-j}$。

使用单调队列优化的动态规划即可。

代码

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
const int N = 1000010;
int a[N*2];
int n;
deque<int> q;

int main () {
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i)
        scanf("%d", &a[i]);
    memcpy(a+1+n, a+1, sizeof(int)*n);
    int halfn = n/2;
    n = 2*n;
    int ans = 0;
    q.push_back(1);
    for (int i = 2; i <= n; ++i) {
        while (q.size() != 0 && q.front()<i-halfn)
            q.pop_front();
        int j = q.front();
        ans = max(ans, a[i]+a[j]+i-j);
        while (q.size() !=0 && a[q.back()]-q.back() <= a[i]-i)
            q.pop_back();
        q.push_back(i); 
    }
    printf("%d\n", ans);
    return 0;
}