您的位置: 首页  >  IT文章  >  学习笔记：四边形不等式优化 DP 定义 & 等价形式 1D/1D 优化 例题 2D/1D 优化

学习笔记：四边形不等式优化 DP 定义 & 等价形式 1D/1D 优化 例题 2D/1D 优化

分类: IT文章 • 2024-05-28 17:38:49

四边形不等式是定义在整数集上的二元函数 (w(x, y))。

定义：对于任意 (a le b le c le d)，满足交叉小于等于包含（即 (w(a, c) + w(b, d) le w(b, c) + w(a, d))。①

等价形式，对于任意的 (a < b)，都有 (w(a, b-1) + w(a+1,b) le w(a+1, b-1)+w(a,b))。②

① 推 ② 看定义即可，② 推 ① 的证明：

任取 (a < d)，(w(a, d-1) + w(a+1,d le w(a+1,d-1) + w(a,d))

若 (a + 1 < d)，(w(a+1, d-1) + w(a+2,d) le w(a+2,d-1) + w(a+1,d))

两式相加：(w(a+2,d) + w(a, d-1) le w(a,d) + w(a+2,d-1))

可扩展到对于任意的 (a le a + k = b le d)， (w(b,d) + w(a, d-1) le w(a,d) + w(b,d-1))

同理 (c - 1) 也可扩展到 (c - k)，因此可扩展到 (a le b le c le d) 的形式。

1D/1D 优化

形如： $f_i = underset{0le j<i}{min}{{f_j+w(j, i)}} $。

若 (w) 满足四边形不等式：

① 则 (f_i) 具有最优决策单调性（即 (p_i) 表示 (f_i) 的最优决策 (j)，则 (p) 非严格递增）。

② 且不仅最优决策有单调性，任意决策都有决策单调性（若 (u < v) 且在当前 (i) 时 (v) 优于 (u)，则 (i < i') 的 (i') 时 (u) 也比 (v) 优）。

证明（证明了 ②，自然 ① 也成立）：

任取 (0 le u < v < i < i')，若有 (f_u + w(u,i) ge f_v + w(v, i)) ③ 即在 (i) 时 (v) 比 (u) 优。

由四边形不等式 (w(u, i) + w(v, i') le w(v, i) + w(u, i') Leftrightarrow w(u, i') - w(u, i) ge w(v, i') - w(v, i))。④

③ 和 ④ 式相加得证。

因此，我们可以动态决策，维护就当前有的决策来说，每个位置的局部最优决策，加入前 (i - 1) 的决策后，当前 (f_i) 的决策就能得到，然后我们考虑加入 (i) 这个决策能作为哪些 (f) 的最优决策。由上述性质，(i) 影响的是一段后缀。因此我们要快速找出后缀的开头，可二分（后缀里 (i) 最优，后缀前 (i) 不优），但是我们如果暴力修改可能还是 (O(n^2))，因此我们可以把每个决策把其作为最优决策的区间一段一段的存。

具体做法：

  • 每个决策存 (x, l, r) 三个变量，分别代表决策、影响的区间左右端点。维护一个决策的队列。

  • 每次从队尾迭代：如果该区间队头都是 (i) 更优那么把这个决策删了；否则如果队尾 (i) 不优就退出；否则二分那个边界的位置。

复杂度：

  • 每个决策最多删除增加一次，插入删除是 (O(n)) 的。

  • 每次最多二分一次，这部分是 (O(n log n)) 的。

因此总复杂度 (O(n log n))。

例题

NOI2009 诗人小G

设 (l) 为长度数组，(S) 为 (l) 前缀和。

朴素 DP 方程：(f_i = underset{0le j < i}{min} { f_j + |S_i - S_j + i - j - 1 - L| ^ P})

证明 (w(j, i) = |S_i - S_j + i - j - 1 - L| ^ P) 满足决策单调性。

(w(j+1,i) - w(j+1, i+1) ge v(j,i) - v(j,i+1))。

设 (v) 是 (w) 那一坨去掉 (P) 次方。

设 (a = v(j, i), b = v(j + 1, i))。

(|b|^P - |b+l_{i+1}+1|^P ge |a|^P - |a+l_{i+1} + 1|)

即证明 (y = |x|^P - |x+c|^P (c > 0)) 函数非严格递减。

由于本人数学太差不会求导，只能感性证一下，首先看 (P = 1) 的情况，是以 ((-c/2, 0)) 中心对称的一个函数，然后这个东西的物理意义就是到数轴上 (x) 到原点的距离 (-) 到 ((-c, 0)) 的距离，分类讨论之后是递减的。如果有 (P) 次方是把这个影响扩大化，但是仍满足相对大小关系。

#include <cstdio>
#include <iostream>
#include <cstring>
using namespace std;
typedef long long LL;
typedef long double LD;
const int N = 100005;
int n, L, P, s[N], hh, tt, pre[N];
LD f[N];
char g[N][35];
struct Q{
	int l, r, x;
} q[N];
/*
f[i] = f[j] + val(i, j)
val(i, j) = (s[i] - s[j] - (i - j - 1) - L) ^ P
*/
LD val(int i, int j) {
	LD res = 1; 
	int x = abs(s[i] - s[j] + (i - j - 1) - L);
	for (int k = 1; k <= P; k++) res *= x;
	return res + f[j];
}

void insert(int i) {
	int pos = -1;
	while (hh <= tt) {
		if (val(q[tt].l, i) <= val(q[tt].l, q[tt].x)) pos = q[tt--].l;
		else {
			if (val(q[tt].r, i) < val(q[tt].r, q[tt].x)) {
				int l = q[tt].l, r = q[tt].r;
				while (l < r) {
					int mid = (l + r) >> 1;
					if (val(mid, i) <= val(mid, q[tt].x)) r = mid;
					else l = mid + 1;
				}
				q[tt].r = r - 1, pos = r;
			}
			break;
		}
	}
	if (pos != -1) q[++tt] = (Q) { pos, n, i };
}

void print(int i) {
    if (!i) return;
    print(pre[i]);
    for (int j = pre[i] + 1; j <= i; j++) {
        printf("%s", g[j] + 1);
        if (j != i) putchar(' ');
    }
    puts("");
}

int main() {
	int T; scanf("%d", &T);
	while (T--) {
	    memset(pre, 0, sizeof pre);
		scanf("%d%d%d", &n, &L, &P);
		for (int i = 1; i <= n; i++) {
			scanf("%s", g[i] + 1);
			s[i] = s[i - 1] + strlen(g[i] + 1);
		}
		hh = tt = 1;
		q[1] = (Q) { 1, n, 0 };
		for (int i = 1; i <= n; i++) {
			int j = q[hh].x;
			f[i] = val(i, j);
			pre[i] = j;
			while (hh <= tt && q[hh].r <= i) hh++;
			q[hh].l = i + 1;
			insert(i);
		}
		if (f[n] > 1e18) puts("Too hard to arrange");
		else printf("%lld
", (LL) f[n]), print(n);
		puts("--------------------");
	}
}

2D/1D 优化

定理 1：

① 形如 (f_{i, j} = underset{ile k < j}{min}{ f_{i, k} + f_{k+1, j} + w(i, j) })，② 且 (f_{i, i} = w_{i,i} = 0)。

③ 若 (w) 满足四边形不等式，④ 而且对于任意的 (a le b le c le d) 都有 (w(a,d) ge w(b,c))

若有着四个条件，则 (f) 也满足四边形不等式。

证明：

当 (j - i = 1) 时，(f_{i,j+1}+f_{i+1,j}=f_{i,i+2})

若 (f_{i,i+2}) 最优决策是 (i)：

[f_{i,i+2}=f_{i+1,i+2}+w(i,i+2) \ =w(i+1,i+2)+w(i,i+2) \ ge w(i+1,i+2)+w(i,i+1) \ ge f_{i+1,i+2}+f_{i,i+1}=f_{i,j+1}+f_{i,j} ]

最优决策是 (i+1) 同理。

因此这时候满足四边形不等式。

接着数学归纳法，设 (j - i < k) 时 (f) 的四边形不等式成立（这里 (i, j) 分别作为最小数和次大数），尝试证 (j - i = k) 成立。

然后是一大波分讨。

(i + 1 le x le y)。

设 (f_{i,j+1}) 和 $f_{i+1,j} $ 的最优决策分别是 (x) 、 (y)。

(f_{i,j+1}+f_{i+1,j} = f_{i, x} + f_{x+1,j+1}+w(i,j+1) + f_{i+1,y}+f_{y+1,j}+w(i+1,j)) ①

(f_{i,j}+f_{i+1,j+1} le f_{i,x}+f_{x+1,j}+w(i,j)+f_{i+1,y}+f_{y+1,j+1}+w(i+1,j+1) ②) ②

根据前面的四边形不等式有：

(w(i, j) + w(i+1,j+1) le w(i,j+1) + w(i+1, j))

(f_{x+1,j}+f_{y+1,j+1}le f_{x+1,j+1}+f_{y+1,j})，这里因为 (j - (x + 1) < j - i = k) 所以成立。

所以 ① ② 可以用不等号连起来，就有了 (f_{i,j}+f_{i+1,j+1}le f_{i,j+1}+f_{i+1,j})，就证完了。

(i + 1 le y le x)。

与上述证明类似。

定理 2

若上述那个式子的 (f) 满足四边形不等式，设 (p_{i, j}) 为 (f_{i,j}) 的最优决策。

则有：$$p_{i,j-1} le p_{i,j} le p_{i+1,j}$$

设 (p = p_{i,j}, i < k le p)，有 (f_{i,p} + f_{i+1,k} ge f_{i+1,k} + f_{i+1,p} Leftrightarrow f_{i+1,k} - f_{i+1,p} ge f_{i,k} - f_{i,p})

(p) 的最优性有 (f_{i,k}+f_{k+1,j} ge f_{i,p}+f_{p+1,j})。

[f_{i+1,k}+f_{k+1,j}+w(i+1,j) - (f_{i+1,p} + f_{p+1,j} + w(i+1,j)) \ ge (f_{i,k} - f_{i,p}) + (f_{k+1,j} - f_{p+1,j}) = (f_{i,k}+f_{k+1},j) - (f_{i,p}+f_{p+1,j}) \ ge 0 ]

因此对于 (f_{i+1,j})，选 (p) 比所有的 (k < p) 都优，因此 (p_{i,j} le p_{i+1,j})。

(p_{i,j-1} le p_{i,j}) 同理。

因此我们每次循环决策可以就询问 ([p_{i,j-1}, p_{i+1,j}])，这样是 (O(n^2)) 的。

复杂度证明，枚举 (f_{i,j}) 的最优决策复杂度是 (p_{i+1,j} - p_{i,j-1}) 量级的。把所有的求和，发现每个 (p_{l, r}) 除非某一位是 (n) 或 (1)，否则会分别有一正一负的抵消贡献，剩下的是部分最多 (2n) 项每一项都是 (le n)（甚至还有负的，所以总共 (O(n^2))。

例题 石子合并

(n = 5000) 的石子合并。

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;

const int N = 5005;

int n, f[N][N], p[N][N], s[N];

int main() {
    memset(f, 0x3f, sizeof f);
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        scanf("%d", s + i), s[i] += s[i - 1];
        f[i][i] = 0, p[i][i] = i;
    }
    for (int l = 2; l <= n; l++) {
        for (int i = 1, j; (j = i + l - 1) <= n; i++) {
            for (int k = p[i][j - 1]; k <= p[i + 1][j]; k++) {
                if (f[i][k] + f[k + 1][j] + s[j] - s[i - 1] < f[i][j]) {
                    f[i][j] = f[i][k] + f[k + 1][j] + s[j] - s[i - 1], p[i][j] = k;
                    
                }
            }
        }
    }
    printf("%d
", f[1][n]);
}

相关推荐