P6173 分治+DP
Usada_Pekora
·
·
题解
我用的是官方题解中提到的利用分治优化 O(n^3 k) 的暴力程序的做法。优化后复杂度为 O(n^2k \log n) 。
设 f[i][j] 表示到了 j-1 位置一共开了 i 扇门。 f[0][n] 初始化为 0 。（有一维起点隐藏掉了） 。
直接跑显然是不行的，枚举起点、开门数、终点、开门点需要 $O(n^3 k)$ 的复杂度。
如果计算第 $i$ 个门在 $f[i][n/2]$ 中的位置，那么对于 $j<n/2$ 的 $f[i][j]$ 必须在其左侧，对于 $j>n/2$ 的 $f[i][j]$ 必须在其右侧。通过这种方式，我们可以在递归的每个级别平均将搜索空间减半。这样就将复杂度降了一个级别。也就是 $O(n^2k \log n)$ 。
```cpp
#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
using namespace std;
const int N = 1005, K = 10;
#define INF 0x3fffffffffffffff
int t, n, k;
long long a[N], f[K][N], s[N][N];
inline int pos(int x, int y) {
return x+y>=n?x+y-n:x+y;
}
inline long long calc(int a, int b) {
return s[pos(a, t)][pos(b, n - a)];
}
inline void dfs(int k, int x1, int x2, int y1, int y2) {
if (x1 == x2) return;
int midx = (x1 + x2) >> 1;
int midy = -1;
f[k][midx] = INF;
for (int j = max(midx + 1, y1); j < y2; j++) {
long long v = f[k - 1][j] + calc(midx, j);
if (v < f[k][midx]) {
midy = j;
f[k][midx] = v;
}
}
dfs(k, x1, midx, y1, midy + 1);
dfs(k, midx + 1, x2, midy, y2);
return;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(NULL);
cin >> n >> k;
for (int i = n - 1; ~i; i--) cin >> a[i];
for (int i = 0; i < n; i++) {
long long sum = 0;
for (int j = 1; j <= n; j++) {
s[i][j] = s[i][j - 1] + sum;
sum += a[pos(i, j - 1)];
}
}
memset(f, 63, sizeof(f));
long long ans = INF;
f[0][n] = 0;
for (t = 0; t < n; t++) {
for (int i = 1; i <= k; i++) dfs(i, 0, n, 1, n + 1);
ans = min(ans, f[k][0]);
}
cout << ans << '\n';
return 0;
}
```