决策单调性优化
对于形如
\[f_i = \min_{j = 0}^{i - 1} \{ f_j + w(j, i) \} \]的转移方程，记 \(p_i\) 为令 \(f_i\) 取得最小值的 \(j\) 的值（最优决策点）。若 \(p\) 单调不降，则称 \(f\) 具有决策单调性。
四边形不等式
以上述转移方程为例，四边形不等式的一个形式为：
若对于任意 \(a \leq b \leq c \leq d\) 均满足：
\[w(a, c) + w(b, d) \leq w(a, d) + w(b, c) \]则称函数 \(w\) 满足四边形不等式，简记为交叉优于包含。
若恒取等，则称 \(w\) 满足四边形恒等式。
可以证明若 \(w\) 满足四边形不等式，则上述转移方程满足决策单调性。
四边形不等式的另一个形式为：
若对于任意 \(i \leq j\) 均满足：
\[w(i, j) + w(i + 1, j + 1) \leq w(i, j + 1) + w(i + 1, j) \]则称函数 \(w\) 满足四边形不等式。
在此引入一个概念：区间包含单调性：
对于任意 \(a \leq b \leq c \leq d\) 均满足：
\[w(b, c) \leq w(a, d) \]则称函数 \(w\) 满足区间包含单调性，简记为内优于外。
四边形不等式的一些性质：
- 若函数 \(w_1(i, j), w_2(i, j)\) 均满足四边形不等式，则对于任意 \(c_1, c_2 \geq 0\) ，函数 \(c_1 w_1 + c_2 w_2\) 也满足四边形不等式。
- 若存在函数 \(f(x), g(x)\) 使得 \(w(i, j) = f(i) - g(j)\) ，则函数 \(w\) 满足四边形恒等式。若 \(f(x), g(x)\) 单调增，则函数 \(w\) 还满足区间包含单调性。
- 设 \(h(x)\) 是一个单调增加的下凸函数，若函数 \(w(i, j)\) 满足四边形不等式和区间包含单调性，则复合函数 \(h(w(i, j))\) 也满足四边形不等式和区间包含单调性。
- 设 \(h(x)\) 是一个下凸函数，若函数 \(w(i, j)\) 满足四边形恒等式和区间包含单调性，则复合函数 \(h(w(i, j))\) 也满足四边形不等式。
一类特殊转移方程的队列优化
使用条件
一般形式为：对于任意两个决策 \(j_1 < j_2\) ，存在一个 \(x\) 满足 \(i \leq x\) 时 \(j_1\) 优于 \(j_2\) ，\(i > x\) 时 \(j_1\) 劣于 \(j_2\) 。
可以证明基于四边形不等式的转移方程同样满足该条件。
特殊的是该条件可以不满足决策单调性，形式为：对于任意两个决策 \(j_1 < j_2\) ，存在一个 \(x\) 满足 \(i \leq x\) 时 \(j_1\) 劣于 \(j_2\) ，\(i > x\) 时 \(j_1\) 优于 \(j_2\) 。
队列优化
建立一个队列维护决策点，队列中保存若干三元组 \((j, l, r)\) ，表示最优决策点为 \(j\) 的区间为 \([l, r]\) 。
遍历枚举 \(i\) ，执行以下操作：
- 检查队头：设队头为 \((j_0, l_0, r_0)\) ，若 \(r_0 = i - 1\) ，则删除队头；否则令 \(l_0 \leftarrow i\) 。
- 取队头保存最优决策点 \(j\) 进行转移求出 \(f_i\) 。
- 尝试插入新决策 \(i\) ，步骤如下：
- 取出队尾，记为 \((j_t, l_t, r_t)\) 。
- 若对于 \(f_{l_t}\) 来说， \(i\) 决策优于 \(j_t\) 决策，记 \(pos = l_t\) ，删除队尾重新执行上一步。
- 否则若对于 \(f_{r_t}\) 来说，\(i\) 决策优于 \(j_t\) 决策，则在 \([l_t, r_t]\) 上二分查找位置 \(pos\) ，满足 \([pos, n]\) 的最优决策点均为 \(i\) 。
- 将三元组 \((i, pos, n)\) 插入队尾。
时间复杂度 \(O(n \log n)\) 。
\[f_i = \min (f_j + |(s_i - s_j) + (i - j) - (L + 1)|^P) \]
按上述方法实现即可。
#include <bits/stdc++.h>
typedef long double ldb;
using namespace std;
const int N = 1e5 + 7, S = 3e1 + 7;
struct Node {
int l, r, j;
} q[N];
ldb f[N];
int s[N], g[N];
bool ed[N];
char str[N][S];
int n, L, P, head, tail;
template <class T = int>
inline T read() {
char c = getchar();
bool sign = c == '-';
while (c < '0' || c > '9')
c = getchar(), sign |= c == '-';
T x = 0;
while ('0' <= c && c <= '9')
x = (x << 1) + (x << 3) + (c & 15), c = getchar();
return sign ? (~x + 1) : x;
}
inline ldb mi(ldb a, int b) {
ldb res = 1;
for (; b; b >>= 1, a *= a)
if (b & 1)
res *= a;
return res;
}
inline ldb calc(int i, int j) {
return f[j] + mi(abs(s[i] - s[j] - L), P);
}
inline int BinarySearch(int l, int r, int i, int j) {
int pos = r + 1;
while (l <= r) {
int mid = (l + r) >> 1;
if (calc(mid, i) <= calc(mid, j))
pos = mid, r = mid - 1;
else
l = mid + 1;
}
return pos;
}
signed main() {
int T = read();
while (T--) {
n = read(), L = read() + 1, P = read();
for (int i = 1; i <= n; ++i) {
scanf("%s", str[i]);
s[i] = s[i - 1] + strlen(str[i]) + 1;
}
q[head = tail = 1] = (Node) {1, n, 0};
for (int i = 1; i <= n; ++i) {
if (q[head].r == i - 1)
++head;
f[i] = calc(i, g[i] = q[head].j);
int pos = n + 1;
while (head <= tail) {
if (calc(q[tail].l, i) <= calc(q[tail].l, q[tail].j))
pos = q[tail--].l;
else {
pos = BinarySearch(q[tail].l, q[tail].r, i, q[tail].j);
q[tail].r = pos - 1;
break;
}
}
if (pos != n + 1)
q[++tail] = (Node) {pos, n, i};
}
if (f[n] > 1e18)
puts("Too hard to arrange");
else {
printf("%.0LF\n", f[n]);
fill(ed + 1, ed + 1 + n, false);
for (int i = n; i; i = g[i])
ed[i] = true;
for (int i = 1; i <= n; ++i)
printf("%s%c", str[i], " \n"[ed[i]]);
}
puts("--------------------");
}
return 0;
}
二分栈优化
用单调栈维护所有有用的决策，其中栈顶是当前最优决策。
计算完 \(f_i\) 后，考虑求决策点为 \(i\) 的后缀。由于决策单调性，所以可以二分。
具体地，每次将 \(i\) 与栈顶的决策比较，若栈顶的决策区间内 \(i\) 恒优则弹栈，否则求出分界点后修改栈顶决策区间并压入 \(i\) 及相关后缀。
将一个数列分成若干段，从每一段中选定一个数 \(s_0\) ，假设这个数有 \(t\) 个，则这一段价值为 \(s_0 t^2\) 。求每一段的价值和的最大值。
\(n \leq 10^5\)
不难得到转移方程：
\[f_i = \max_{j = 1}^{i} \{ f_{j - 1} + s_i \times (sum_i - sum_j + 1)^2 \} \]可以发现最优决策点一定满足 \(s_i = s_j\) ，否则独立成段更优。于是固定 \(j\) 时，\(s_i \times (sum_i - sum_j + 1)^2\) 单调递增。故对于一个 \(j_1 < j_2\) ，存在一个分界点满足分界点前 \(j_1\) 更优，分界点后 \(j_2\) 更优。于是有决策单调性，用二分栈优化即可。
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
const int N = 1e5 + 7;
vector<int> sta[N];
ll f[N];
int a[N], buc[N], s[N];
int n, top;
template <class T = int>
inline T read() {
char c = getchar();
bool sign = (c == '-');
while (c < '0' || c > '9')
c = getchar(), sign |= (c == '-');
T x = 0;
while ('0' <= c && c <= '9')
x = (x << 1) + (x << 3) + (c & 15), c = getchar();
return sign ? (~x + 1) : x;
}
inline ll calc(int j, int t) {
return f[j - 1] + 1ll * a[j] * t * t;
}
inline int check(int x, int y) {
int l = 1, r = n, ans = n + 1;
while (l <= r) {
int mid = (l + r) >> 1;
if (calc(x, mid - s[x] + 1) >= calc(y, mid - s[y] + 1))
ans = mid, r = mid - 1;
else
l = mid + 1;
}
return ans;
}
signed main() {
n = read();
for (int i = 1; i <= n; ++i)
s[i] = ++buc[a[i] = read()];
for (int i = 1; i <= n; ++i) {
int c = a[i];
#define tp1 sta[c][sta[c].size() - 1]
#define tp2 sta[c][sta[c].size() - 2]
while (sta[c].size() >= 2 && check(tp2, tp1) <= check(tp1, i))
sta[c].pop_back();
sta[c].emplace_back(i);
while (sta[c].size() >= 2 && check(tp2, tp1) <= s[i])
sta[c].pop_back();
f[i] = calc(tp1, s[i] - s[tp1] + 1);
#undef tp1
#undef tp2
}
printf("%lld", f[n]);
return 0;
}
整体二分优化
某些 DP 形式如下：
\[f_{i, j} = \min_{k \leq j} (f_{i - 1, k} + w(k, j)) \ \ \ \ (1 \leq i \leq n, 1 \leq j \leq m) \]其中 \(i \in [1, n], j \in [1, m]\) ，共 \(n \times m\) 个状态，每个状态有 \(O(m)\) 个决策，时间复杂度 \(O(nm^2)\) 。
令 \(m_{i, j}\) 为上述转移中最小化 \(k\) 的值，若 \(\forall i, j, m_{i, j} \leq m_{i, j + 1}\) ，则我们可以用分治优化。
假设我们对于固定的 \(i, j\) 计算 \(m_{i, j}\) ，那么我们可以确定 \(\forall j' < j, m_{i, j'} < m_{i, j}\) ，这意味着计算 \(m_{i, j'}\) 时不用考虑那么多其他的点
运用分治思想，递归得到 \(m\) 的上下界，就可以达到 \(O(nm \log m)\) 的时间复杂度，每个 \(m_{i, j}\) 的值只可能出现在 \(\log m\) 个不同点中。
Yet Another Minimization Problem
给定一个序列 \(a_{1 \sim n}\) ，要把它分成 \(k\) 个子段。每个子段的费用是其中相同元素的对数，求所有子段的费用之和的最小值。
\(n \leq 10^5, k \leq \min(n, 20)\)
设 \(f_{i, j}\) 表示前 \(i\) 个元素分为 \(j\) 段的最小费用，\(w(l, r)\) 表示 \([l, r]\) 的费用，则：
\[f_{i, j} = \max (f_{k - 1, j - 1} + w(k, i)) \]不难发现 \(w(l, r)\) 满足四边形不等式，故 \(f\) 每一层的转移都具有决策单调性。令 solve(l, r, L, R) 表示 \(f_{i, [L, R]}\) 的决策点在 \([l, r]\) 中，则可以每次计算出 \(f_{i, mid}\) 的决策点，将序列分为两部分分治。
接卸来考虑如何计算 \(f_{i, mid}\) 的决策点，直接计算时困难的，可以类似莫队维护一个指针。分治时相邻两次 \(mid\) 的改变量加起来应与 \(R - L\) 同级，故右端点移动次数为 \(O(n \log n)\) ；左端点一定从上一次分治的某个端点移动而来，在此次分治内移动次数与 \(r - l\) 同级，也是 \(O(n \log n)\) 。
总时间复杂度 \(O(nk \log n)\) 。
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
const ll inf = 1e18;
const int N = 1e5 + 7, K = 2e1 + 7;
ll f[N][K];
int a[N];
int n, k;
template <class T = int>
inline T read() {
char c = getchar();
bool sign = (c == '-');
while (c < '0' || c > '9')
c = getchar(), sign |= (c == '-');
T x = 0;
while ('0' <= c && c <= '9')
x = (x << 1) + (x << 3) + (c & 15), c = getchar();
return sign ? (~x + 1) : x;
}
namespace MoAlgorithm {
int cnt[N];
ll result;
int l = 1, r = 0;
inline void add(int x) {
result += cnt[a[x]]++;
}
inline void del(int x) {
result -= --cnt[a[x]];
}
inline ll calc(int ql, int qr) {
while (l > ql)
add(--l);
while (r < qr)
add(++r);
while (l < ql)
del(l++);
while (r > qr)
del(r--);
return result;
}
} // namespace MoAlgorithm
void solve(int l, int r, int L, int R, const int d) {
if (L > R)
return;
int mid = (L + R) >> 1, mnpos = 0;
f[mid][d] = inf;
for (int i = l; i <= min(mid, r); ++i) {
ll res = f[i - 1][d - 1] + MoAlgorithm::calc(i, mid);
if (res < f[mid][d])
f[mid][d] = res, mnpos = i;
}
solve(l, mnpos, L, mid - 1, d), solve(mnpos, r, mid + 1, R, d);
}
signed main() {
n = read(), k = read();
for (int i = 1; i <= n; ++i)
a[i] = read();
for (int i = 1; i <= n; ++i)
f[i][0] = inf;
for (int i = 1; i <= k; ++i)
solve(1, n, 1, n, i);
printf("%lld", f[n][k]);
return 0;
}
P3515 [POI2011] Lightning Conductor
给出 \(a_{1 \sim n}\) ，对于每个 \(i \in [1, n]\) ，求一个最小的非负整数 \(p\) ，使得对于所有 \(j \in [1, n]\) 都有 \(a_j \leq a_i + p - \sqrt{|i - j|}\) 。
\(n \leq 5 \times 10^5\)
转化限制条件为：
\[p + a_i \geq \max_{j = 1}^n \{ a_j + \sqrt{|i - j|} \} \]将绝对值拆开，正反各做一次，得到：
\[p + a_i \geq \max_{j = 1}^{i - 1} \{ a_j + \sqrt{i - j} \} \]记 \(w(j, i) = \sqrt{i - j}\) ，则 \(w(j, i)\) 满足四边形不等式，于是 \(f_i = \max_{j = 1}^{i - 1} \{ a_j + \sqrt{i - j} \}\) 满足决策单调性。
#include <bits/stdc++.h>
using namespace std;
const int N = 5e5 + 7;
double a[N], sq[N], f[N];
int n;
template <class T = int>
inline T read() {
char c = getchar();
bool sign = (c == '-');
while (c < '0' || c > '9')
c = getchar(), sign |= (c == '-');
T x = 0;
while ('0' <= c && c <= '9')
x = (x << 1) + (x << 3) + (c & 15), c = getchar();
return sign ? (~x + 1) : x;
}
inline double calc(int j, int i) {
return a[j] + sq[i - j];
}
void solve(int l, int r, int L, int R) {
if (L > R)
return;
int mid = (L + R) >> 1, mxpos = l;
double mx = calc(l, mid);
for (int i = l + 1; i <= min(r, mid); ++i)
if (calc(i, mid) > mx)
mxpos = i, mx = calc(i, mid);
f[mid] = max(f[mid], calc(mxpos, mid));
solve(l, mxpos, L, mid - 1), solve(mxpos, r, mid + 1, R);
}
signed main() {
n = read();
for (int i = 1; i <= n; ++i)
a[i] = read(), sq[i] = sqrt(i);
solve(1, n, 1, n);
reverse(a + 1, a + 1 + n), reverse(f + 1, f + 1 + n);
solve(1, n, 1, n);
reverse(a + 1, a + 1 + n), reverse(f + 1, f + 1 + n);
for (int i = 1; i <= n; ++i)
printf("%d\n", (int)ceil(f[i] - a[i]));
return 0;
}
Knuth's optimization
有一个结论，设 \(p_{i, j}\) 为 \(f_{i, j}\) 的最优决策点 \(k\) ，若 \(f_{i, j}\) 满足四边形不等式，则 \(\forall i < j, p_{i, j - 1} \leq p_{i, j} \leq p_{i + 1, j}\) 。
如对于一类区间 DP：
\[f_{i, j} = \min_{k = i}^{j - 1} \{ f_{i, k} + f_{k + 1, j} \} + w(i, j) \]若 \(w\) 满足四边形不等式和区间包含单调性，则 \(f(i, j)\) 也满足四边形不等式。
则我们枚举 \([l, r]\) 的决策时，只要在 \([p_{l, r - 1}, p_{l + 1, r}]\) 中枚举决策即可，可以证明总时间复杂度为 \(O(n^2)\) 。
for (int len = 2; len <= n; ++len)
for (int l = 1, r = len; r <= n; ++l, ++r) {
f[l][r] = inf;
for (int k = p[l][r - 1]; k <= p[l + 1][r]; ++k)
if (f[l][r] > f[l][k] + f[k + 1][r] + w(l, r)) {
f[l][r] = f[l][k] + f[k + 1][r] + w(l, r);
p[l][r] = k;
}
}
有 \(n\) 个村庄，放 \(m\) 个邮局，求每个村庄到最近邮局的距离和的最小值。
\(n \leq 3000, m \leq 300\)
设 \(f_{i, j}\) 表示前 \(i\) 个村庄放 \(j\) 个邮局的最小距离和，\(w(l, r)\) 表示在 \([l, r]\) 范围村庄放一个邮局的最小距离和，则有：
\[f_{i, j} = \min_{k = 0}^{i - 1} \{ f_{k, j - 1} + w(k + 1, i) \} \]可以证明 \(w(l, r)\) 满足四边形不等式，于是可以决策单调性优化做到 \(O(n^2)\) 。
当然也可以打表发现四边形不等式与决策单调性。
#include <bits/stdc++.h>
using namespace std;
const int inf = 0x3f3f3f3f;
const int N = 3e3 + 7, M = 3e2 + 7;
int w[N][N], f[N][M], g[N][M];
int a[N];
int n, m;
signed main() {
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; ++i)
scanf("%d", a + i);
sort(a + 1, a + 1 + n);
for (int l = 1; l <= n; ++l)
for (int r = l + 1; r <= n; ++r)
w[l][r] = w[l][r - 1] + (a[r] - a[(l + r) >> 1]);
memset(f, inf, sizeof(f));
f[0][0] = 0;
for (int j = 1; j <= m; ++j) {
g[n + 1][j] = n;
for (int i = n; i; --i)
for (int k = g[i][j - 1]; k <= g[i + 1][j]; ++k)
if (f[k][j - 1] + w[k + 1][i] <= f[i][j])
f[i][j] = f[k][j - 1] + w[k + 1][i], g[i][j] = k;
}
printf("%d", f[n][m]);
return 0;
}
应用
给出 \(n\) 个区间，将它们分为两份满足两份区间没有交，可以丢弃区间。
第一问：求两份区间数量较小者的最大值。
第二问：对于所有 \(i \in [1, n]\) ，求强制选取第 \(i\) 个区间时的第一问。
\(n \leq 200\)
首先将时间离散化，设时间值域为 \([1, m]\) 。
设 \(cnt(l, r)\) 表示被 \([l, r]\) 完全包含的区间个数，不难 \(O(n^3)\) 预处理得到。
再设 \(f_{i, j}\) 表示以 \(i\) 开始的前缀时刻选择 \(j\) 个区间到第一份，此时第二份最多能选区间的数量。不难得到转移方程：
\[f_{i, j} = \max_{k = 1}^{i - 1} \{ f_{k, j - cnt(k + 1, i)}, f_{k, j} + cnt(k + 1, i) \} \]答案即为：
\[\max_{i = 0}^n \{ \min(f_{m, i}, i) \} \]于是第一问可以 \(O(n^3)\) 解决。
对于第二问，钦定强制不丢弃的区间在第一份。设 \(g_{i, j}\) 表示以 \(i\) 开始的后缀时刻选择 \(j\) 个区间到第一份，此时第二份最多能选区间的数量。转移与 \(f\) 是类似的。
那么强制选取的区间 \([l, r]\) 给第二份后，于是有：
\[\max_{i = 1}^{l - 1} \max_{j = r + 1}^m \max_{k = 0}^n \max_{t = 0}^n \min(f_{i, k} + g_{j, t}, k + t + cnt(i + 1, j -1 )) \]注：因为两份区间地位等价，于是可以钦定 \(cnt(i + 1, j + 1)\) 放第二份。
直接做是 \(O(n^4)\) 的，考虑优化。设：
\[h(l, r) = \max_{i = 0}^n \max_{j = 0}^n \min(f_{l, i} + f_{r, j}, i + j + cnt(l + 1, r - 1)) \]则答案即为 \(\max_{i = 1}^{l - 1} \max_{j = r + 1}^m h(l, r)\) ，这一部分可以做到 \(O(n^2)\) 。
接下来考虑如何计算 \(h(l, r)\) 。可以发现 \(\min\) 里面的东西是两份的区间数，由于两份区间地位是相同的，所以会在 \(\min\) 中按两种顺序都会出现。于是可以直接认为 \(k + t + cnt(l + 1, r - 1)\) 是较大值。
接下来问题转化为在右边为较大值的情况下最大化左边的值，注意到 \(f_{l, i}\) 随 \(i\) 的增大而减小，\(g_{r, j}\) 随 \(j\) 的减小而减小。那么当 \(i\) 增加时再减小 \(j\) 显然不优，因此可以单纯减小左、右两边。这一部分时间复杂度降为 \(O(n^3)\) 。
总时间复杂度 \(O(n^3)\) 。
#include <bits/stdc++.h>
using namespace std;
const int inf = 0x3f3f3f3f;
const int N = 2e2 + 7, M = 4e2 + 7;
pair<int, int> interval[N];
int cnt[M][M], f[M][N], g[M][N], h[M][M];
int n, m;
signed main() {
scanf("%d", &n);
vector<int> vec = {-inf, inf};
for (int i = 1; i <= n; ++i) {
scanf("%d%d", &interval[i].first, &interval[i].second);
interval[i].second += interval[i].first - 1;
vec.emplace_back(interval[i].first), vec.emplace_back(interval[i].second);
}
sort(vec.begin(), vec.end());
vec.erase(unique(vec.begin(), vec.end()), vec.end());
for (int i = 1; i <= n; ++i) {
interval[i].first = lower_bound(vec.begin(), vec.end(), interval[i].first) - vec.begin() + 1;
interval[i].second = lower_bound(vec.begin(), vec.end(), interval[i].second) - vec.begin() + 1;
}
m = vec.size();
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= interval[i].first; ++j)
for (int k = interval[i].second; k <= m; ++k)
++cnt[j][k];
fill(f[0] + 1, f[0] + 1 + n, -inf);
for (int i = 1; i <= m; ++i)
for (int j = 0; j <= n; ++j) {
f[i][j] = -inf;
for (int k = 0; k < i; ++k) {
if (f[k][j] != -inf)
f[i][j] = max(f[i][j], f[k][j] + cnt[k + 1][i]);
if (f[k][max(j - cnt[k + 1][i], 0)] != -inf)
f[i][j] = max(f[i][j], f[k][max(j - cnt[k + 1][i], 0)]);
}
}
int ans = 0;
for (int i = 0; i <= n; ++i)
ans = max(ans, min(f[m][i], i));
printf("%d\n", ans);
fill(g[m + 1] + 1, g[m + 1] + 1 + n, -inf);
for (int i = m; i; --i)
for (int j = 0; j <= n; ++j) {
g[i][j] = -inf;
for (int k = i + 1; k <= m + 1; ++k) {
if (g[k][j] != -inf)
g[i][j] = max(g[i][j], g[k][j] + cnt[i][k - 1]);
if (g[k][max(j - cnt[i][k - 1], 0)] != -inf)
g[i][j] = max(g[i][j], g[k][max(j - cnt[i][k - 1], 0)]);
}
}
for (int i = 1; i <= m; ++i)
for (int j = i + 2; j <= m; ++j) {
h[i][j] = -inf;
for (int k = 0, t = n; k <= n && f[i][k] != -inf; ++k) {
while (~t) {
if (min(f[i][k] + g[j][t], k + t + cnt[i + 1][j - 1]) >= h[i][j])
h[i][j] = min(f[i][k] + g[j][t], k + t + cnt[i + 1][j - 1]);
else
break;
--t;
}
++t;
}
}
for (int i = 1; i <= n; ++i) {
int ans = 0;
for (int j = 1; j < interval[i].first; ++j)
for (int k = interval[i].second + 1; k <= m; ++k)
ans = max(ans, h[j][k]);
printf("%d\n", ans);
}
return 0;
}
给定排列 \(p_{1 \sim n}\) ，将 \(p\) 划分成 \(k\) 段，使每一段的顺序对个数和最小。
\(n \leq 2.5 \times 10^4, k \leq 25\)
设 \(f_{i, j}\) 表示前 \(i\) 个数分为 \(j\) 段的答案，\(w(l, r)\) 表示 \(p_{l \sim r}\) 的顺序对个数，则：
\[f_{i, j} = \min_{k = 0}^{i - 1} \{ f_{k, j - 1} + w(k + 1, i) \} \]注意到这里的 \(w(l, r)\) 并不好求，于是考虑采用整体二分维护决策单调性配合莫队+树状数组求顺序对优化即可，时间复杂度 \(O(nk \log^2 n)\) 。
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
const ll inf = 1e18;
const int N = 2.5e4 + 7, K = 27;
ll f[N][K];
int a[N];
int n, k;
namespace MoAlgorithm {
namespace BIT {
int c[N];
inline void update(int x, int k) {
for (; x <= n; x += x & -x)
c[x] += k;
}
inline int query(int x) {
int res = 0;
for (; x; x -= x & -x)
res += c[x];
return res;
}
} // namespace BIT
ll result;
int l = 1, r = 0;
inline ll calc(int ql, int qr) {
while (l > ql) {
--l;
BIT::update(a[l], 1);
result += (r - l + 1) - BIT::query(a[l]);
}
while (r < qr) {
++r;
result += BIT::query(a[r]);
BIT::update(a[r], 1);
}
while (l < ql) {
result -= (r - l + 1) - BIT::query(a[l]);
BIT::update(a[l], -1);
l++;
}
while (r > qr) {
BIT::update(a[r], -1);
result -= BIT::query(a[r]);
r--;
}
return result;
}
} // namespace MoAlgorithm
void solve(int l, int r, int L, int R, const int d) {
if (L > R)
return;
int mid = (L + R) >> 1, mnpos = 0;
f[mid][d] = inf;
for (int i = l; i <= min(mid, r); ++i) {
ll res = f[i - 1][d - 1] + MoAlgorithm::calc(i, mid);
if (res < f[mid][d])
f[mid][d] = res, mnpos = i;
}
solve(l, mnpos, L, mid - 1, d), solve(mnpos, r, mid + 1, R, d);
}
signed main() {
scanf("%d%d", &n, &k);
for (int i = 1; i <= n; ++i)
scanf("%d", a + i);
for (int i = 1; i <= n; ++i)
f[i][0] = inf;
for (int i = 1; i <= k; ++i)
solve(1, n, 1, n, i);
printf("%lld", f[n][k]);
return 0;
}