$四边形不等式$
已知二元函数 $f(n, m)$ ,若
$\forall a, b, c, d,$ 且 $a\leq b\leq c \leq d$ 都有 $f(a, d) + f(b, c) \ge f(a, c) + f(b, d)$
则称 $f$ 函数满足四边形不等式。
$四边形不等式的判定$
-
对于所有满足 $a\leq b\leq c \leq d$ 的正整数 $a, b, c, d$ 有 $f(a, d) + f(b, c) \ge f(a, c) + f(b, d)$
-
对于所有满足 $i < j$ 的正整数 $i, j$ 有 $f(i, j + 1) + f(i + 1, j) \ge f(i, j) + f(i + 1, j + 1)$
$四边形不等式优化$
四边形不等式应用于 $\textrm{dp}$ 中,若转移方程形如:
$$f_i = \min_{j = 1}^{i - 1} f_j + V_{j, i}$$
且 $V$ 函数满足四边形不等式,那么 $f$ 具有决策单调性。
「决策单调性」
若位置 $p$ 对于 $i$ 而言满足 $\forall j < p , f_j + V_{j, i} \ge f_p + V_{p, i}$
那么对于所有 $i’ > i$ 的所有位置而言也满足 $\forall j < p , f_j + V_{j, i’} \ge f_p + V_{p, i’}$
证明:
已知 $V$ 满足四边形不等式,即
$$V_{j, i’} + V_{p, i} \ge V_{j, i} + V_{p, i’}$$
又由于满足
$$ f_j + V_{j, i} \ge f_p + V_{p, i}$$
将两个不等式相加,得
$$f_j + V_{j, i’} \ge f_p + V_{p, i’}$$
证毕
由此得出结论,若 $p_i$ 表示为 $f_i$ 决策时最优秀的 $j$ ,那么 $p_i$ 非严格单调递增。
$实现$
以 「诗人小 $G$ 」为例。
#include <bits/stdc++.h>
using namespace std;
typedef long double LD;
const int N = 100010;
int n, L, P, hh, tt;
int s[N], opt[N];
LD f[N];
char str[N][40];
struct Node {
int j, l, r;
} q[N];
LD val(int j, int i) {
LD res = 1, t = abs(s[i] - s[j] + i - j - 1 - L);
for (int i = 0; i < P; i ++ ) res *= t;
return res + f[j];
}
void insert(int i) {
int pos = n + 1;
while (hh <= tt && val(q[tt].j, q[tt].l) >= val(i, q[tt].l)) pos = q[tt -- ].l;
if (hh <= tt && val(q[tt].j, q[tt].r) >= val(i, q[tt].r)) {
int l = q[tt].l, r = q[tt].r;
while (l < r) {
int mid = l + r >> 1;
if (val(q[tt].j, mid) >= val(i, mid)) r = mid;
else l = mid + 1;
}
pos = l;
q[tt].r = l - 1;
}
if (pos != n + 1) q[++ tt] = {i, pos, n};
}
int main() {
int T;
scanf("%d", &T);
while (T -- ) {
scanf("%d%d%d", &n, &L, &P);
for (int i = n; i >= 1; i -- ) scanf("%s", str[i]);
for (int i = 1; i <= n; i ++ ) s[i] = s[i - 1] + strlen(str[i]);
hh = tt = 0;
q[0] = {0, 1, n};
for (int i = 1; i <= n; i ++ ) {
f[i] = val(q[hh].j, i), opt[i] = q[hh].j;
if (q[hh].r == i) hh ++ ;
q[hh].l = i + 1;
insert(i);
}
if (f[n] > 1e18) puts("Too hard to arrange");
else {
printf("%lld\n", (long long)f[n]);
for (int i = n; i; i = opt[i])
{
for (int j = i; j > opt[i]; j -- )
{
printf("%s", str[j]);
if (j != opt[i] + 1) printf(" ");
}
puts("");
}
}
puts("--------------------");
}
return 0;
}