环形DP，顾名思义就是在环上做DP，一般这类问题都会与环有关
解法大体分下列几种
###先断环为链，然后强制连接首尾的普通DP
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
| #include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
typedef long long LL;
int n, m;
LL a[100010];
LL dp[2][4010][2];
int main()
{
scanf("%d%d", &n, &m);
LL ans = 0;
for (register int i = 1;i <= n;i ++)scanf("%lld", &a[i]);
for (register int i = 2;i <= n;i ++)//第一次DP，假装这道题是一道在链上DP的水题
{
dp[i & 1][1][1] = dp[(i & 1) ^ 1][0][0];
dp[i & 1][1][0] = max(dp[(i & 1) ^ 1][1][0], dp[(i & 1) ^ 1][1][1]);
for (register int j = 2;j <= m && j <= i;j ++)
{
dp[i & 1][j][1] = max(dp[(i & 1) ^ 1][j - 1][0], dp[(i & 1) ^ 1][j - 1][1] + a[i]);
dp[i & 1][j][0] = max(dp[(i & 1) ^ 1][j][1], dp[(i & 1) ^ 1][j][0]);
}
}
ans = max(dp[n & 1][m][1], dp[n & 1][m][0]);
memset(dp, 0, sizeof(dp));
dp[1 & 1][1][1] = a[1];//第二次DP，强制连接首尾
for (register int i = 2;i <= n;i ++)
{
dp[i & 1][1][1] = dp[(i & 1) ^ 1][0][0];
dp[i & 1][1][0] = max(dp[(i & 1) ^ 1][1][0], dp[(i & 1) ^ 1][1][1]);
for (register int j = 2;j <= m && j <= i;j ++)
{
dp[i & 1][j][1] = max(dp[(i & 1) ^ 1][j - 1][0], dp[(i & 1) ^ 1][j - 1][1] + a[i]);
dp[i & 1][j][0] = max(dp[(i & 1) ^ 1][j][1], dp[(i & 1) ^ 1][j][0]);
}
}
ans = max(ans, dp[n & 1][m][1]);//强制选择最后一项
printf("%lld\n", ans);
}
|
由此得出结论，环形DP的一类解法就是先跑一遍假的普通DP，再跑一遍强制首尾相接的DP，最后两部分合并得出答案。
###直接破环为链，倍长区间的DP
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
| #include <bits/stdc++.h>
using namespace std;
#define MAXN 110
#define INF 0x3f3f3f3f
int n;
int a[MAXN << 1], dp1[MAXN << 1][MAXN << 1], b[MAXN << 1], dp2[MAXN << 1][MAXN << 1];//开两倍大小的数组，因为我们把区间扩大到了原来的两倍
int main()
{
scanf("%d", &n);
for (register int i = 1;i <= n;i ++) scanf("%d", &a[i]), a[n + i] = a[i];//a[n + i] = a[i]使得区间被复制一边
for (register int i = 1;i <= (n << 1);i ++) b[i] = b[i - 1] + a[i];//前缀和维护区间和
for (register int len = 2;len <= n;len ++){
for (register int i = 1;i + len - 1 <= (n << 1);i ++){
int j = i + len - 1;
dp1[i][j] = INF;
dp2[i][j] = -INF;
for (register int k = i;k < j;k ++){
dp1[i][j] = min(dp1[i][j], dp1[i][k] + dp1[k + 1][j] + b[j] - b[i - 1]);
dp2[i][j] = max(dp2[i][j], dp2[i][k] + dp2[k + 1][j] + b[j] - b[i - 1]);
}
}
}
int ans1 = INF, ans2 = -INF;
for (register int i = 1;i <= n;i ++){//扫描每一段环上长度为n的区间
ans1 = min(ans1, dp1[i][i + n - 1]);
ans2 = max(ans2, dp2[i][i + n - 1]);
}
printf("%d\n%d\n", ans1, ans2);
}
|
使用循环数组
越界的数组元素，下表模数组长度取余
总结
说到底，环形DP不过是DP的一种，其核心思维主要在于如何把一个环破成一条或多条链，并且要在保证时间复杂度正确的情况下保证正确性，即每一种状态都应该被考虑到，大概就是这样子。
请我一杯咖啡吧！
微信打赏