决策单调性优化 dp

1 决策单调性的定义

1.1 四边形不等式

首先我们定义一个函数 \(w(i,j)\)，如果 \(\forall a,b,c,d \in \mathbb{Z}\)，满足 \(a\le b\le c\le d\)，都有 \(w(a,d)+w(b,c)\ge w(a,c)+w(b,d)\)，则称函数 \(w\) 满足四边形不等式。

如果考虑用图形来表示，我们可以记为 “包含大于相交”。而这就是四边形不等式的基本定义。不过在实际运用中，我们常常需要证明一个函数满足四边形不等式，直接运用的话比较麻烦，所以更常用的形式是下面这个：

• 定义函数 \(w(i,j)\)，如果 \(\forall a,b\in \mathbb{Z}\)，满足 \(a<b\)，都有 \(w(a,b+1)+w(a+1,b)\ge w(a,b)+w(a+1,b+1)\)，则称函数 \(w\) 满足四边形不等式。

证明在这里略去，意义不大。

1.2 决策单调性

如果我们将上面这个函数 \(w(i,j)\) 定义为序列上一个区间 \([i,j]\) 的代价，然后我们要求划分序列的代价和最小值，这就是一个经典的 1D/1D 动态规划问题，我们有转移方程：

\[f_i=\min_{0\le j<i}(f_{j}+w(j,i)) \]

我们记 \(p_i\) 表示当 \(f_i\) 取到最小值时 \(j\) 的值，也就是常说的决策点。如果 \(p_i\) 单调不降，则称 \(f\) 具有决策单调性。那么此时一个重要的结论就是：当 \(w\) 满足四边形不等式时，\(f\) 有决策单调性。

证明考虑归纳。假设 \(1\sim i-1\) 均满足决策单调性，考虑 \(i\) 处转移。

考虑前面的一个点 \(j<i\)，其决策点为 \(p_{j}\)，再考虑一个点 \(k<p_j\)。

根据决策单调性定义，我们有 \(f_k+w(k,j)\ge f_{p_j}+w(p_j,j)\)。

而又由于 \(k<p_j<j<i\)，根据四边形不等式定义，有 \(w(k,i)+w(p_j,j)\ge w(k,j)+w(p_j,i)\)。移项得 \(w(k,i)-w(k,j)\ge w(p_j,i)-w(p_j,j)\)。

将上面两式相加，得到 \(f_k+w(k,i)\ge f_{p_j}+w(p_j,i)\)。

于是 \(p_j\) 一定比 \(k\) 的决策更优，所以 \(p_i\ge p_j\)，得证。

如此，我们可以将 \(O(n^2)\) 的 dp 优化为 \(O(n\log n)\) 或 \(O(n)\)。接下来介绍几种常见的优化方式。

2 决策单调性算法

2.1 二分队列

根据决策单调性，我们知道，对于一个决策点 \(x\)，一定存在一个区间 \([l_x,r_x]\) 满足 \(\forall i\in [l_x,r_x],p_i=x\)。

那么我们维护一个队列，每个元素是一个三元组 \((p,l,r)\)。假如当前要插入 \(i\)，我们先进行转移：

• 考虑当前队首，如果 \(i>r\)，那么弹出队首，直到队首可以转移到 \(i\)。
• 用队首更新 \(i\)。

接下来我们插入 \(i\) 这个转移点：

• 考虑当前队尾 \((p,l,n)\)，如果 \(i\) 转移到 \(l\) 比 \(p\) 更优，那么 \(p\) 就没用了，弹出 \(p\)。
• 重复上述过程直到不存在这样的决策点。此时我们找出 \(i\) 与队尾的分界点即可，在 \(w\) 好求的情况下，这个可以利用二分来实现。

这种方法就被称作二分队列，复杂度显然是 \(O(n\log n)\) 的。在实际实现中没有必要存下每个三元组，对于每个决策点 \(i\)，只需要存储它对应的 \(l\) 即可。

二分队列的优点在于它可以适用于大部分的决策单调性优化，适用性比较广泛；缺点就是要求 \(w\) 比较好求，如果遇到 \(w\) 需要用类似莫队的算法求解的时候可能就寄了。

2.2 整体二分

整体二分适用于离线决策单调性问题。先来解释一下什么是离线决策单调性，大致来讲，其转移方程形如下：

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

这种 dp 求每个位置时，无需先求出该位置之前的 dp 值即可求出 dp 值的式子，就是离线决策单调性。形如上面的 2D/1D 动态规划就是这一类型。

我们考虑利用整体二分来求解这个问题。设 \(\text{Solve}(l,r,L, R)\) 表示当前我们在计算 \(f_{i,l}\sim f_{i,r}\) 的 dp 值，其决策点被限制在 \([L,R]\) 的子问题。

每一层的操作是简单的，我们暴力枚举 \(p\in [L,R]\)，求出 \(mid=\lfloor\tfrac{l+r}{2}\rfloor\) 处的最优决策点 \(p_{mid}\)，然后递归处理 \(\text{Solve}(l,mid-1,L,p_{mid})\) 和 \(\text{Solve}(mid+1,r,p_{mid},R)\) 即可。复杂度是 \(O(n\log n)\) 的。

这个算法的优点就在于如果 \(w\) 需要类似莫队的算法求解（即可以快速挪动左右端点求出）的时候，复杂度依然是 \(O(n\log n)\) 的。因为每一次我们的右端点从 \(l\) 或 \(r\) 挪动到 \(mid\)，左端点从 \(p_l\) 或 \(p_r\) 挪动到 \(p_{mid}\)，复杂度仍然是区间长度，所以是正确的。当然由于整体二分只能求解离线决策单调性，所以并不能完全替代二分队列。

难道二分队列已经无敌了吗？

2.3 分治序列

原博客称其为丐版 LARSCH 算法，原版的 LARSCH 算法太牛了不会，但是这个做法还是相当简单的。

考虑我们最开始给出的 1D/1D 动态规划转移方程：

\[f_i=\min(f_j+w(j,i)) \]

我们考虑一个分治 \(\text{Solve}(l,r)\)，表示我们当前在计算 \(f_l\sim f_r\) 中的 dp 值。同时我们还需要满足以下两个条件：

• \([1,l)\) 中的 dp 值和决策点已经计算完毕。
• \(r\) 在 \([1,l)\) 中的最优决策点已经计算完毕。

依然考虑求出 \(mid=\lfloor\tfrac{l+r}{2}\rfloor\)，暴力枚举 \(p\in[p_{l-1},p_r]\)，用这些转移点更新 \(f_{mid}\)，然后递归处理 \(\text{Solve}(l,mid)\)。接下来暴力枚举 \(p\in [l,mid]\)，用这些转移点更新 \(f_r\)，然后递归处理 \(\text{Solve}(mid+1,r)\)。很显然每次递归的时候都满足上面的条件，并且正确性比较显然。和上面整体二分的复杂度一致，都是 \(O(n\log n)\)。

同时，和整体二分一致，当我们的 \(w\) 需要挪动左右端点求解时，复杂度依然是 \(O(n\log n)\)，证明也是类似的。需要注意的是由于左端点会在决策点区间和序列区间来回跳动，所以如果直接写复杂度会炸。解决方式就是用两个莫队分别跑决策点区间和序列区间。具体看下面的例题代码。

这个做法的优点就是解决了整体二分不能完成在线决策单调性的缺点，同时相较于二分队列存在代码更简单、可以实现 \(w\) 挪动端点的求解，并且复杂度并没有打折扣。所以是一种相当优异的实现方式。

3 例题

例 1 P1912 [NOI2009] 诗人小 G

\(\text{Link}\)

首先先来推一下转移方程，设 \(f_i\) 表示最后一段以 \(i\) 结尾的最小值，\(sl\) 表示诗句长度前缀和，则有：

\[f_i=\min(f_j+|sl_i-sl_j+i-j-1-L|^P) \]

后面的部分就是函数 \(w(i,j)\)，打表发现它满足四边形不等式。事实上这个证明并不是非常平凡，但是这不是我们的重点，因此略过。

那么此时我们知道 \(f\) 具有决策单调性，直接使用上述算法即可，复杂度 \(O(n\log n)\)。

采用二分队列代码如下：

Code

#include <bits/stdc++.h>
#define il inline
using namespace std;
typedef long double db;
const int N = 2e5 + 5;
const int Inf = 2e9;
struct IO {static const int Size = (1 << 21);char buf[Size], *p1, *p2; int st[105], Top;~IO() {clear();}il void clear() {fwrite(buf, 1, Top, stdout); Top = 0;}il char gc() {return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, Size, stdin), p1 == p2) ? EOF : *p1++;}il void pc(const char c) {Top == Size && (clear(), 0); buf[Top++] = c;}il IO &operator >> (char &c) {while(c = gc(), c == ' ' || c == '\n' || c == '\r'); return *this;}template <typename T> il IO &operator >> (T &x) {x = 0; bool f = 0; char ch = gc();while(!isdigit(ch)) {if(ch == '-') f = 1; ch = gc();}while(isdigit(ch)) x = (x << 1) + (x << 3) + (ch ^ 48), ch = gc();f ? x = -x : 0; return *this;}il IO &operator >> (string &s) {s = ""; char c = gc();while(c == ' ' || c == '\n' || c == '\r') c = gc();while(c != ' ' && c != '\n' && c != '\r' && c != EOF) s += c, c = gc();return *this;}il IO &operator << (const char c) {pc(c); return *this;}template <typename T> il IO &operator << (T x) {if(x < 0) pc('-'), x = -x;do st[++st[0]] = x % 10, x /= 10; while(x);while(st[0]) pc('0' + st[st[0]--]);return *this;}il IO &operator << (const string s) {for(auto c : s) pc(c); return *this;}il IO &operator << (const char *s) {for(int i = 0; s[i]; i++) pc(s[i]); return *this;}
}fin, fout;
int Beg;
il db qpow(db a, int b) {db res = 1; for(; b; b >>= 1, a = a * a) if(b & 1) res = res * a; return res;}
int T;
int n, L, P;
string s[N];
int sl[N];
db dp[N];
int pos[N], p[N];
il db W(int l, int r) {return qpow(abs(sl[r] - sl[l] + r - l - 1 - L), P);}
il db V(int l, int r) {return dp[l] + W(l, r);}
int q[N], hd, tl;
il int schpos(int p, int q) {int l = q + 1, r = n, res = n + 1;while(l <= r) {int mid = (l + r) >> 1;if(V(p, mid) > V(q, mid)) res = mid, r = mid - 1;else l = mid + 1;}return res;
}
int vis[N];
il void solve() {fin >> n >> L >> P;for(int i = 1; i <= n; i++) fin >> s[i], sl[i] = sl[i - 1] + s[i].size(), vis[i] = 0;q[hd = tl = 1] = 0; pos[0] = 1; dp[0] = 0;for(int i = 1; i <= n; i++) {while(hd < tl && pos[q[hd + 1]] - 1 < i) hd++;p[i] = q[hd]; dp[i] = V(p[i], i);while(hd < tl && schpos(q[tl], i) <= pos[q[tl]]) tl--;pos[i] = schpos(q[tl], i);q[++tl] = i;}if(dp[n] > 1e18) {fout << "Too hard to arrange\n";}else {fout << (long long)dp[n] << '\n';int ps = n;while(ps) vis[ps] = 1, ps = p[ps];for(int i = 1; i <= n; i++) {fout << s[i] << (!vis[i] ? ' ' : '\n');}}fout << "--------------------\n";
}
int End;
il void Usd() {cerr << (&Beg - &End) / 1024.0 / 1024.0 << "MB " << (double)clock() * 1000.0 / CLOCKS_PER_SEC << "ms\n";}
int main() {fin >> T;while(T--) solve();Usd();return 0;
}

采用分治序列代码如下：

Code

#include <bits/stdc++.h>
#define il inline
using namespace std;
typedef long double db;
const int N = 2e5 + 5;
const int Inf = 2e9;
struct IO {static const int Size = (1 << 21);char buf[Size], *p1, *p2; int st[105], Top;~IO() {clear();}il void clear() {fwrite(buf, 1, Top, stdout); Top = 0;}il char gc() {return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, Size, stdin), p1 == p2) ? EOF : *p1++;}il void pc(const char c) {Top == Size && (clear(), 0); buf[Top++] = c;}il IO &operator >> (char &c) {while(c = gc(), c == ' ' || c == '\n' || c == '\r'); return *this;}template <typename T> il IO &operator >> (T &x) {x = 0; bool f = 0; char ch = gc();while(!isdigit(ch)) {if(ch == '-') f = 1; ch = gc();}while(isdigit(ch)) x = (x << 1) + (x << 3) + (ch ^ 48), ch = gc();f ? x = -x : 0; return *this;}il IO &operator >> (string &s) {s = ""; char c = gc();while(c == ' ' || c == '\n' || c == '\r') c = gc();while(c != ' ' && c != '\n' && c != '\r' && c != EOF) s += c, c = gc();return *this;}il IO &operator << (const char c) {pc(c); return *this;}template <typename T> il IO &operator << (T x) {if(x < 0) pc('-'), x = -x;do st[++st[0]] = x % 10, x /= 10; while(x);while(st[0]) pc('0' + st[st[0]--]);return *this;}il IO &operator << (const string s) {for(auto c : s) pc(c); return *this;}il IO &operator << (const char *s) {for(int i = 0; s[i]; i++) pc(s[i]); return *this;}
}fin, fout;
int Beg;
il db qpow(db a, int b) {db res = 1; for(; b; b >>= 1, a = a * a) if(b & 1) res = res * a; return res;}
int T;
int n, L, P;
string s[N];
int sl[N];
db dp[N];
int p[N];
il db W(int l, int r) {return qpow(abs(sl[r] - sl[l] + r - l - 1 - L), P);}
il db V(int l, int r) {return dp[l] + W(l, r);}
int vis[N];
il void solve(int l, int r) {if(l == r) {dp[l] = V(p[l], l);return ;}int mid = (l + r) >> 1;for(int i = p[l - 1]; i <= p[r]; i++) {if(V(i, mid) < V(p[mid], mid)) p[mid] = i;}solve(l, mid);for(int i = l; i <= mid; i++) {if(V(i, r) < V(p[r], r)) p[r] = i;}solve(mid + 1, r);
}
il void solve() {fin >> n >> L >> P;for(int i = 1; i <= n; i++) fin >> s[i], sl[i] = sl[i - 1] + s[i].size();for(int i = 1; i <= n; i++) vis[i] = p[i] = 0;dp[0] = 0;solve(1, n);if(dp[n] > 1e18) {fout << "Too hard to arrange\n";}else {fout << (long long)dp[n] << '\n';int ps = n;while(ps) vis[ps] = 1, ps = p[ps];for(int i = 1; i <= n; i++) {fout << s[i] << (!vis[i] ? ' ' : '\n');}}fout << "--------------------\n";
}
int End;
il void Usd() {cerr << (&Beg - &End) / 1024.0 / 1024.0 << "MB " << (double)clock() * 1000.0 / CLOCKS_PER_SEC << "ms\n";}
int main() {fin >> T;while(T--) solve();Usd();return 0;
}

例 2 CF868F Yet Another Minimization Problem

\(\text{Link}\)

设 \(f_{i,j}\) 表示当前分到第 \(i\) 段，最后一段以 \(j\) 为结尾的最小值，则有转移方程：

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

容易发现的是，这个 \(w\) 满足四边形不等式，并且可以用莫队直接简单计算得出，所以我们可以采用整体二分求解，复杂度 \(O(n\log n)\)。

采用整体二分实现如下：

Code

#include <bits/stdc++.h>
#define il inline
#define int long long
using namespace std;
const int N = 2e5 + 5;
const int Inf = 1e18;
template <typename T> il void chkmin(T &x, T y) {x = min(x, y);}
template <typename T> il void chkmax(T &x, T y) {x = max(x, y);}
struct IO {static const int Size = (1 << 21);char buf[Size], *p1, *p2; int st[105], Top;~IO() {clear();}il void clear() {fwrite(buf, 1, Top, stdout); Top = 0;}il char gc() {return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, Size, stdin), p1 == p2) ? EOF : *p1++;}il void pc(const char c) {Top == Size && (clear(), 0); buf[Top++] = c;}il IO &operator >> (char &c) {while(c = gc(), c == ' ' || c == '\n' || c == '\r'); return *this;}template <typename T> il IO &operator >> (T &x) {x = 0; bool f = 0; char ch = gc();while(!isdigit(ch)) {if(ch == '-') f = 1; ch = gc();}while(isdigit(ch)) x = (x << 1) + (x << 3) + (ch ^ 48), ch = gc();f ? x = -x : 0; return *this;}il IO &operator >> (string &s) {s = ""; char c = gc();while(c == ' ' || c == '\n' || c == '\r') c = gc();while(c != ' ' && c != '\n' && c != '\r' && c != EOF) s += c, c = gc();return *this;}il IO &operator << (const char c) {pc(c); return *this;}template <typename T> il IO &operator << (T x) {if(x < 0) pc('-'), x = -x;do st[++st[0]] = x % 10, x /= 10; while(x);while(st[0]) pc('0' + st[st[0]--]);return *this;}il IO &operator << (const string s) {for(auto c : s) pc(c); return *this;}il IO &operator << (const char *s) {for(int i = 0; s[i]; i++) pc(s[i]); return *this;}
}fin, fout;
il void File() {freopen(".in", "r", stdin); freopen(".out", "w", stdout);}
int Beg;
int n, k, a[N];
int dp[21][N];
int pl = 1, pr = 0, cnt[N], sum;
il int C2(int x) {return x * (x - 1) / 2;}
il void add(int x) {int p = a[x];sum += cnt[p]; cnt[p]++;
}
il void del(int x) {int p = a[x];cnt[p]--; sum -= cnt[p];
}
il int W(int l, int r) {while(pr < r) add(++pr);while(pl > l) add(--pl);while(pr > r) del(pr--);while(pl < l) del(pl++);return sum;
}
il int V(int x, int l, int r) {return dp[x - 1][l - 1] + W(l, r);
}
int p[N];
il void solve(int x, int l, int r, int pl, int pr) {if(l > r) return ;if(pl == pr) {for(int i = l; i <= r; i++) dp[x][i] = V(x, pl, i);return ;}int mid = (l + r) >> 1;for(int i = pl; i <= pr; i++) {int c = V(x, i, mid);if(c < dp[x][mid]) dp[x][mid] = c, p[mid] = i;}solve(x, l, mid - 1, pl, p[mid]), solve(x, mid + 1, r, p[mid], pr); 
}
int End;
il void Usd() {cerr << (&Beg - &End) / 1024.0 / 1024.0 << "MB " << (double)clock() * 1000.0 / CLOCKS_PER_SEC << "ms\n";}
signed main() {fin >> n >> k;for(int i = 1; i <= n; i++) fin >> a[i];for(int i = 0; i <= k; i++) for(int j = 1; j <= n; j++) dp[i][j] = Inf;dp[0][0] = 0;for(int i = 1; i <= k; i++) {for(int j = 1; j <= n; j++) p[j] = 0;solve(i, 1, n, 1, n);}fout << dp[k][n] << '\n';Usd();return 0;
}

当然了，我们也可以采用分治序列，用两个莫队实现即可：

Code

#include <bits/stdc++.h>
#define il inline
#define int long long
using namespace std;
const int N = 2e5 + 5;
const int Inf = 1e18;
template <typename T> il void chkmin(T &x, T y) {x = min(x, y);}
template <typename T> il void chkmax(T &x, T y) {x = max(x, y);}
struct IO {static const int Size = (1 << 21);char buf[Size], *p1, *p2; int st[105], Top;~IO() {clear();}il void clear() {fwrite(buf, 1, Top, stdout); Top = 0;}il char gc() {return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, Size, stdin), p1 == p2) ? EOF : *p1++;}il void pc(const char c) {Top == Size && (clear(), 0); buf[Top++] = c;}il IO &operator >> (char &c) {while(c = gc(), c == ' ' || c == '\n' || c == '\r'); return *this;}template <typename T> il IO &operator >> (T &x) {x = 0; bool f = 0; char ch = gc();while(!isdigit(ch)) {if(ch == '-') f = 1; ch = gc();}while(isdigit(ch)) x = (x << 1) + (x << 3) + (ch ^ 48), ch = gc();f ? x = -x : 0; return *this;}il IO &operator >> (string &s) {s = ""; char c = gc();while(c == ' ' || c == '\n' || c == '\r') c = gc();while(c != ' ' && c != '\n' && c != '\r' && c != EOF) s += c, c = gc();return *this;}il IO &operator << (const char c) {pc(c); return *this;}template <typename T> il IO &operator << (T x) {if(x < 0) pc('-'), x = -x;do st[++st[0]] = x % 10, x /= 10; while(x);while(st[0]) pc('0' + st[st[0]--]);return *this;}il IO &operator << (const string s) {for(auto c : s) pc(c); return *this;}il IO &operator << (const char *s) {for(int i = 0; s[i]; i++) pc(s[i]); return *this;}
}fin, fout;
il void File() {freopen(".in", "r", stdin); freopen(".out", "w", stdout);}
int Beg;
int n, k, a[N];
int dp[21][N];
il int C2(int x) {return x * (x - 1) / 2;}
struct MQ {int pl = 1, pr = 0, cnt[N], sum;il void add(int x) {int p = a[x];sum += cnt[p]; cnt[p]++;}il void del(int x) {int p = a[x];cnt[p]--; sum -= cnt[p];}il int W(int l, int r) {while(pr < r) add(++pr);while(pl > l) add(--pl);while(pr > r) del(pr--);while(pl < l) del(pl++);return sum;}il int V(int x, int l, int r) {return dp[x - 1][l] + W(l + 1, r);}
}A, B;
int p[N];
il void solve(int x, int l, int r) {if(l > r) return ;if(l == r) {dp[x][l] = A.V(x, p[l], l);return ;}int mid = (l + r) >> 1;for(int i = p[l - 1]; i <= p[r]; i++) {int c = A.V(x, i, mid);if(c < dp[x][mid]) dp[x][mid] = c, p[mid] = i;}solve(x, l, mid);for(int i = l; i <= mid; i++) {int c = B.V(x, i, r);if(c < dp[x][r]) dp[x][r] = c, p[r] = i;}solve(x, mid + 1, r);
}
int End;
il void Usd() {cerr << (&Beg - &End) / 1024.0 / 1024.0 << "MB " << (double)clock() * 1000.0 / CLOCKS_PER_SEC << "ms\n";}
signed main() {fin >> n >> k;for(int i = 1; i <= n; i++) fin >> a[i];for(int i = 0; i <= k; i++) for(int j = 1; j <= n; j++) dp[i][j] = Inf;dp[0][0] = 0; p[0] = 1;for(int i = 1; i <= k; i++) {for(int j = 1; j <= n; j++) p[j] = 0;solve(i, 1, n);}fout << dp[k][n] << '\n';Usd();	return 0;
}

例 3 P9266 [PA 2022] Nawiasowe podziały

\(\text{Link}\)

首先发现这个段数非常大，直接求的话复杂度肯定爆炸。容易想到随着段数的增大，答案单调不增，也就是构成了一个下凸包。那么我们可以先使用 wqs 二分进行优化，转化成一维 dp。

设 \(f_i\) 表示最后一段结尾在 \(i\) 的方案数，则转移方程为：

\[f_i=\min(f_j+w(j+1,i)-mid) \]

现在考虑 \(w\) 怎么求。我们知道括号序列可以转化为 \(1,-1\) 序列，设其前缀和为 \(s_i\)。那么一个 \([l,r]\) 的括号序合法当且仅当 \(s_{l-1}=s_r=\min\limits_{l\le i\le r}s_i\)。

我们考虑利用莫队来求出 \(w\)。考虑一个点 \(i\) 与其前面的点的贡献，我们求出 \(pos_i\) 表示 \(i\) 前面最后一个满足 \(s_j<s_i\) 的 \(j\) 的位置，那么我们只需要求出当前 \((pos_i,i)\) 中有多少个 \(s\) 的值等于 \(s_i\) 即可。可以用线段树直接做，不过不太牛。

这样表述比较麻烦，我们改一下描述。我们将 \(s_i\) 相同且 \(pos_i\) 相同的 \(i\) 放到同一组内，不难发现同一组内的任意一对数都可以选择，中间不会有 \(<s_i\) 的数出现。事实上这就是广义笛卡尔树的结构，那么我们每次加入一个点的时候用莫队统计一下贡献即可。

总复杂度是 \(O(n\log n\log V)\)，在本题数据范围下足够通过。

4 区间 dp 决策单调性

我们知道区间 dp 有一个经典形式，设 \(f_{i,j}\) 表示区间 \([i,j]\) 的最小代价，转移方程为：

\[f_{i,j}=\min(f_{i,k}+f_{k+1,j})+w(i,j) \]

那么当函数 \(w\) 满足一定条件的时候，我们就可以使用决策单调性优化 dp。首先要满足的当然是四边形不等式，而另外一个需要满足的是区间包含单调性：

• 如果 \(\forall a,b,c,d\in \mathbb{Z}\)，都有 \(w(b,c)\le w(a,d)\)，则称 \(w\) 满足区间包含单调性。

则此时 \(f\) 具有决策单调性。如果我们设 \(p_{i,j}\) 表示 \(f_{i,j}\) 的最优决策点 \(k\)，那么会有 \(p_{i,j-1}\le p_{i,j}\le p_{i+1,j}\)，而此时我们直接枚举 \([p_{i,j-1},p_{i+1,j}]\) 即可将复杂度降到 \(O(n^2)\)。

经典例题就是石子合并了，这里不再赘述。