概览
对于环形的问题又应该怎么做呢?不再是像朴素的一样是找区间的分割点
题解
关键,看作一个环,实际是进行连边操作,看能够连多少边。
- 直接枚举最后一步的缺口在哪里,然后拉开转化为链式问题。
> 实际上就是枚举,但是这种枚举破开的方式,关键是怎么看待其实每个边的地位都一样这件事
> n^4 - 本质是什么?本质是求n个长度为n的链
> 将环形链复制在后面,复制一遍,实际就是对2n的链上做. 牛逼!!
> 非常巧妙!!2n^3
todo: 总结环形问题是否都可以这样解决,处理决定多数环形问题
代码
1.一维迭代式
循环长度,循环左端点
for (int len = 1; len <= n; len )
for (int l = 1; l + len - 1 <= n; l )
r = l + len - 1;
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int N = 420, INF = 0x3f3f3f3f;
int n;
int s[N], w[N];
int f[N][N], g[N][N];
int main() {
cin >> n;
for (int i = 1; i <= n; i ++) {
cin >> w[i];
w[i + n] = w[i];
}
for (int i = 1; i <= n * 2; i ++) s[i] = s[i - 1] + w[i];
memset(f, 0x3f, sizeof f);
memset(g, -0x3f, sizeof g);
for (int len = 1; len <= n; len ++)
for (int l = 1; l + len - 1 <= n * 2; l ++) {
int r = l + len - 1;
if (len == 1) f[l][r] = g[l][r] = 0;
else {
for (int k = l; k < r; k ++) {
f[l][r] = min(f[l][r], f[l][k] + f[k + 1][r] + s[r] - s[l - 1]);
g[l][r] = max(g[l][r], g[l][k] + g[k + 1][r] + s[r] - s[l - 1]);
}
}
}
int minv = INF, maxv = - INF;
for (int i = 1; i <= n; i ++) {
minv = min(minv, f[i][i + n - 1]);
maxv = max(maxv, g[i][i + n - 1]);
}
cout << minv << endl << maxv << endl;
return 0;
}