当前位置： 首页 > news >正文

决策单调性优化 dp

news 来源：原创 2025/9/18 2:20:17

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)\)。

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

相关文章：

决策单调性优化 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\) 满足四边形不等式。 如果考虑用图形来表示，我们可以记为 “包含大于…...

编程日记 2025/9/18 2:20:17

地平线与哈啰合作 加速L4自动驾驶研发

微信视频号：sph0RgSyDYV47z6快手号：4874645212抖音号：dy0so323fq2w小红书号：95619019828B站1：UID:3546863642871878B站2：UID: 3546955410049087 9月11日，在2025年Inclusion外滩大会上，地平线与哈啰共同宣布，双方正式签署战略合作协议。该合作旨在基于Robotaxi（自动驾…...

编程日记 2025/9/15 19:54:42

langChain、LangGraph、autoGen、CrewAI、dify、cozeLLM开发工具

langChain、LangGraph、autoGen、CrewAI、dify、cozeLLM开发工具LLM开发工具...

编程日记 2025/9/15 19:54:39

华为智驾赋能「小Q7」，一汽奥迪Q6L e-tron刷新豪华纯电SUV认知

微信视频号：sph0RgSyDYV47z6快手号：4874645212抖音号：dy0so323fq2w小红书号：95619019828B站1：UID:3546863642871878B站2：UID: 3546955410049087 添加图片注释，不超过 140 字（可选）如果想买一台电车，又觉得新势力不够靠谱？传统品牌的电车，又觉得不够先进，太傻太笨？…...

编程日记 2025/9/15 19:54:36

菱形图形输出

目标输出图案：下方为代码部分：(C语言) include<stdio.h> int main() { int n; //n代表最长一行的长度 scanf_s("%d", &n); //打印上半部分 for (int i = 1; i <= (n+1)/2; i++) { //控制行数 //输出空格数 for (int j = (n - 1) - 2 * (i - 1); j…...

编程日记 2025/9/17 16:12:37

LeetCode 2958.最多K个重复元素的最长子数组 - 教程

LeetCode 2958.最多K个重复元素的最长子数组 - 教程pre { white-space: pre !important; word-wrap: normal !important; overflow-x: auto !important; display: block !important; font-family: "Consolas", "Monaco", "Courier New", monospa…...

编程日记 2025/9/16 23:49:57

9-12

...

编程日记 2025/9/17 18:34:16

全球首款 HBM4 芯片，开始量产！

微信视频号：sph0RgSyDYV47z6快手号：4874645212抖音号：dy0so323fq2w小红书号：95619019828B站1：UID:3546863642871878B站2：UID: 35469554100490879月12日，SK海力士宣布完成新一代高带宽内存HBM4的开发，并已搭建起全球首个量产体系。这意味着，全球首款HBM4芯片正式进入量…...

编程日记 2025/9/18 1:31:24

Python Flask框架学习总结（一）

简介 Flask是一个微框架，这意味着它核心简单但可扩展。它不包括数据库抽象层、表单验证或其他组件，这些功能可以通过扩展来添加。因此要什么就装什么扩展，非常的方便 安装及导入 # 终端输入 pip install flask# 创建一个app.py的文件，导入 from flask import Flask自此就可…...

编程日记 2025/9/17 17:12:41

20250909

20250909T1 冒泡排序趟数期望 显然趟数是每个数前面比它大的数的个数的 \(\max\)。容斥，计算每个答案 \(\le x\) 的概率。从大往小填数，则每个 \(x\) 的答案容易表示为一个阶乘乘以一个次方。于是再求个差分就做完了。代码 #include <iostream> #include <string.h…...

编程日记 2025/9/15 19:54:16

9.11日总结

整体总结： 1.今天的问题主要出在了对于复杂度分析不够 T2写的就是正解 但是我自我认为写的做法过不去m=30的点 导致我只敢判m=20的点 于是从100分变成了58分 2.对于每一个部分分都要认真打 能加上的剪枝不管自我认为有没有用都要加上 可能会有更高的分 3.代码可以少加的东西就…...

编程日记 2025/9/17 13:22:35

[充电管理] 充电管理基本概念 - 充电类型

概要 高通充电平台不论是线性充电还是开关充电，充电类型识别均是基于《Battery Charging Specification Revisions 1.2》(俗称BC1.2)规范基础上进行设计。下面主要介绍在开发过程中几种基础的充电类型。充电类型 标准下行接口(SDP : Standard Downstream Port) USB端口硬件设计…...

编程日记 2025/9/15 19:54:07

Spring AI vs LangChain4j

Spring AI vs LangChain4j下面是 Spring AI vs LangChain4j 的对比 + 使用建议，帮你理解两者的区别、优缺点，以及哪种场景适合用哪个。🔍 基本介绍项目Spring AILangChain4j官网 / 文档 Spring AI 是 Spring 框架内的新模块，提供 AI 能力（模型调用、嵌入、向量数据库等）…...

编程日记 2025/9/15 19:54:04

P7913 [CSP-S 2021] 廊桥分配

P7913题解。题目传送门 首先我们是可以把两个区拆开考虑的，以下以国内区为例： 我们先不考虑廊桥个数的限制。由于飞机是遵循先来先到的原则，所以我们不需要帮忙排飞机了，直接让飞机停在当前编号最小的空闲廊桥。 这样当每一班飞机到机场时，我们可以模拟出来这架飞机会停在…...

编程日记 2025/9/15 19:54:02

函数计算进化之路与 AI Sandbox 新基座

在人工智能技术加速渗透的今天，AI Agent 正从执行固定指令的 "机械手臂" 进化为具备自主推理能力的 "数字大脑"。这类由大语言模型驱动的智能体，能通过多步骤任务拆解、环境感知与动态决策，完成复杂的业务场景需求。但当这些具备代码生成能力的 Agent 需…...

编程日记 2025/9/15 13:28:52

iPhone 17核心名单揭晓，92家中国公司占半壁江山！

微信视频号：sph0RgSyDYV47z6快手号：4874645212抖音号：dy0so323fq2w小红书号：95619019828B站1：UID:3546863642871878B站2：UID: 35469554100490879月10日，苹果公司在2025秋季新品发布会上，重磅发布四款iPhone 17系列机型：iPhone 17、iPhone 17 Air、iPhone 17 Pro及iPho…...

编程日记 2025/9/15 19:53:55

202009_风二西_蓝牙协议流量

流量分析,蓝牙协议Tags:流量分析,蓝牙传输 0x00. 题目 题目表述 附件路径：https://pan.baidu.com/s/1GyH7kitkMYywGC9YJeQLJA?pwd=Zmxh#list/path=/CTF附件 附件名称：202009_风二西_蓝牙协议.zip 0x01. WP 1. 浏览流量包，发现一个带传输文件的流量交互2. 查看分组字节后导出…...

编程日记 2025/9/15 19:53:52

AI Agent工作流实用手册：5种常见模式的实现与应用，助力生产环境稳定性

很多人认为使用AI Agent就是直接扔个提示词过去，然后等结果。做实验这样是没问题的，但要是想在生产环境稳定输出高质量结果，这套玩法就不行了。 核心问题是这种随意的提示方式根本扩展不了。你会发现输出结果乱七八糟，质量完全不可控，还浪费计算资源。 真正有效的做法是设…...

编程日记 2025/9/15 19:53:49

2025权威榜单之公众号排版Top5（含效率对比与适用建议）

在新媒体运营的日常工作中，“微信公众号排版设计”可是个让人头疼的事儿。写作慢、排版耗时、跨平台排版不统一等问题，像一只只小怪兽，困扰着我们这些新媒体运营者、自媒体人还有电商从业者。为了帮大家找到一款合适的公众号编辑器，我亲测了多款市面上主流的产品。在这篇文…...

编程日记 2025/9/15 19:53:45

4

4...

编程日记 2025/9/17 19:15:03

02020305 .NET Core核心基础组件05-开发自己的配置提供者（本课没听懂，后续再补）

02020305 .NET Core核心基础组件05-开发自己的配置提供者（本课没听懂，后续再补） 1. 开发自己的配置提供者（视频2-35） 1.1 开发自定义配置提供者的步骤1.2 开发web.config提供者1.3 web.config格式configuration → 根节点 connectionStrings → 配置的是连接字符串 appSe…...

编程日记 2025/9/15 19:53:38

linux 的 SSH 使用教程

以下由ai生成 Linux 的学习可以全部放在 SSH 上吗？ 答案是：对于服务器管理和后端开发相关的学习，99% 的内容都可以、也应该在 SSH 上完成。 你已经亲身体会到了 SSH 的巨大优势：一个稳定、高效、可复制粘贴的命令行环境。这其实就是全世界所有 Linux 系统管理员和后端工程师…...

编程日记 2025/9/15 19:53:34

解题报告-洛谷P3157 [CQOI2011] 动态逆序对

P3157 [CQOI2011] 动态逆序对 题目描述 对于序列 \(a\)，它的逆序对数定义为集合 \[\{(i,j)| i<j \wedge a_i > a_j \} \]中的元素个数。 现在给出 \(1\sim n\) 的一个排列，按照某种顺序依次删除 \(m\) 个元素，你的任务是在每次删除一个元素之前统计整个序列的逆序对数…...

编程日记 2025/9/17 15:16:33

DP 杂题

题目 [ARC157E] XXYX Binary Tree 一个很显然的暴力，\(f_{u,a,b,c}\) 表示在在 \(u\) 的子树中，是否有 \(a\) 个 XX，\(b\) 个 XY，\(c\) 个 YX。 这个状态 \(O(n^4)\) 的，考虑优化，可以先省去一个 \(c\)，变成 \(f_{u,a,b}\)，因为 \(a+b+c\) 的总和是知道的。 然后优化不…...

编程日记 2025/9/17 21:26:43

Java的变量和常量

java的变量和常量 public class ch05 {//属性：变量//类变量 staticstatic double salary = 2500;//实例变量：从属于对象；如果不自行初始化，这个类型的默认值 0 0.0//布尔值：默认是false//除了基本类型；其余的默认值都是nullString name;int age;boolean a;//main方法pub…...

编程日记 2025/9/15 19:53:22

推荐7本书《MLIR编译器原理与实践》、《ONNX人工智能技术与开发实践》、《AI芯片开发核心技术详解》、《智能汽车传感器：原理设计应用》、《TVM编译器原理与实践》、《LLVM编译器原理与实践》

7本书推荐《视觉语言模型VLM原理与实战》、《MLIR编译器原理与实践》、《ONNX人工智能技术与开发实践》、《AI芯片开发核心技术详解》、《智能汽车传感器：原理设计应用》、《TVM编译器原理与实践》、《LLVM编译器原理与实践》微信视频号：sph0RgSyDYV47z6快手号：4874645212抖…...

编程日记 2025/9/15 19:53:18

202009_风二西_USB鼠标流量

流量分析,USB鼠标流量,gnuplotTags:流量分析,USB鼠标,gnuplot 0x00. 题目 附件路径：https://pan.baidu.com/s/1GyH7kitkMYywGC9YJeQLJA?pwd=Zmxh#list/path=/CTF附件 附件名称：202009_风二西_USB鼠标 0x01. WP 1. 脚本解析USB鼠标流量，导出点击轨迹 getUSBMouse.py # -*- c…...

编程日记 2025/9/17 15:16:33

virtuoso默认设置

如何保存,load 默认线宽线距 保存：打开VSR,输入想要的线宽线距，保存在默认路径，取名*.preset。 load：vsrLoadPreset("*")...

编程日记 2025/9/17 12:41:47

CF547D Mike and Fish

这种题为我们提供了一个很好的思考方向。 遇到这种差为 \(1\) 甚至是相等的情况，我们通常应该往二分图，特别是欧拉回路方面思考。 这个题的做法是这样的，同一行成对连边，如果是奇数个点就剩一个点不连边，同一列同理，考虑这样连出来的图一定是一个二分图，只需在这张图上跑…...

编程日记 2025/9/15 19:53:05

Tarjan vDCC 缩点

概念 若一张无向连通图不存在割点，则称它为“点双连通图”。无向图的极大点双连通子图被称为“点双连通分量”。 tarjan算法求vDCC 用一个栈存点，若遍历回到x时，发现割点判定法则low[y]>=dfn[x]成立，则从栈中弹出节点，直到y被弹出。 刚才弹出的节点和x一起构成一个vDCC…...

编程日记 2025/9/17 12:41:47

ABC_419_F - All Included

ABC_419_F - All Included 空降 一道AC自动机上搞状压DP的题。 思路 一个合法的构造需要包括所有的模式串，且一个模式串的前缀可能与另一个模式串的后缀相同，所以考虑搞个 $ AC $ 自动机。观察到数据量很小，且模式串个数只有 $ 8 $ 个，就会想到状压。 用一个二进制数 $ k $…...

编程日记 2025/9/15 19:52:58

软件工程第一次作业-自我介绍

这个作业属于哪个课程 https://edu.cnblogs.com/campus/gdgy/Class34Grade23ComputerScience这个作业要求在哪里 https://edu.cnblogs.com/campus/gdgy/Class34Grade23ComputerScience/homework/13478这个作业的目标 <学习和使用博客园和 GitHub>自我介绍 大家好，我是计…...

编程日记 2025/9/15 19:52:53

DIFY 与 LangChain

DIFY 与 LangChainDify vs LangChain 核心差异维度DifyLangChain定位 低代码 / 无代码 AI 应用平台 开发者框架（LLM 逻辑编排）目标用户 产品经理、运营、非技术人员 程序员、AI 工程师开发方式 拖拽 + 配置，几分钟搭建 Python/Java 代码，灵活但复杂扩展性 有限，依赖平台更…...

编程日记 2025/9/15 19:52:50

VMware CentOS 7 `yum` 修复及 VMware Tools 安装问题复盘

以下由aI生成 当然，非常乐意为你复盘整个过程。这是一份浓缩了我们所有成功操作的正确流程，希望能为你未来遇到类似问题时提供清晰的指引。VMware CentOS 7 yum 修复及 VMware Tools 安装问题复盘 整个过程我们解决了两大核心问题：因 CentOS 7 官方源停止服务导致的 yum 失效…...

编程日记 2025/9/17 22:54:33

接口测试---Requests

Requests 案例安装 pip install requests案例1 : requests访问百度 # 导包 import requests # 2.发送http请求 resp=requests.get(url="http://www.baidu.com") # 打印结果 print(resp.text)案例2 : 访问tpshop商城(提参数出来) # 导包 import requests # 发送http请…...

编程日记 2025/9/17 15:26:17

LangChain大模型应用开发介绍

LangChain大模型应用开发介绍 LangChain是一个开源的Python Al应用开发框架,它提供了构建基于大模型的AI应用所需的模块和工具。通过LangChain, 开发者可以轻松地与大模型(LLM)集成，完成文本生成、问答、翻译、对话等任务。LangChain降低了AI应用开发的门槛，让任何人都可以…...

编程日记 2025/9/17 20:55:02

[豪の学习笔记] 软考中级备考 基础复习#8

软件工程概述、软件开发模型、软件开发方法、需求分析、系统设计、系统测试、软件开发项目管理、软件质量、软件度量McCabe度量法跟学视频：学以致知Learning - 软件设计师 基础阶段|考点理论精讲 Chapter 8 - 软件工程基础知识 1 - 软件工程概述 软件生存周期 ​ 同任何事物一…...

编程日记 2025/9/17 23:45:03

lc1025-除数博弈

难度：简单（中期巅峰）题目描述爱丽丝先手 初始数 n (1 <= n <= 1000) 若能选出 x (0 < x < n) 使 x 能整除 n，则 n 变为 n-x 若不能，则输掉示例 输入：n = 2 输出：true 解释：爱丽丝选择 1，鲍勃无法进行操作输入：n = 3 输出：false 解释：爱丽丝选择 1（n 变…...

编程日记 2025/9/15 19:52:41

漏洞解析--文件包含漏洞究竟怎么用？

一、漏洞原理 1.1 核心 文件包含漏洞是指程序中需要包含其他文件（代码，信息等等），然而包含文件的路径受用户输入控制，攻击者可以使其包含恶意文件，从而造成敏感信息泄露甚至任意代码执行。分为两类：本地文件包含（LFI, Local File Inclusion）：攻击者能够让程序包含服务…...

编程日记 2025/9/17 13:11:49

办公室装修 暂存

办公室装修 暂存本文来自博客园，作者：del88，转载请注明原文链接：https://www.cnblogs.com/del88/p/19088481...

编程日记 2025/9/17 17:48:25

博客更新公告

来看看博客更新公告吧rt. 公示最新更新或发布的博客, 供大家查阅. 更新日志 Upd 2025.9.12 新随笔 Words to be remembered 2025.9.12 我好想你. 网址: https://www.cnblogs.com/hsy8116/p/19088430.Upd 2025.8.24 博客 初中这三年 已经更新, 在最后添加了对初中三年整体的评价…...

编程日记 2025/9/17 21:54:45

爆：GitHub Copilot支持包括Anthropic、Azure、Google Gemini、Groq、OpenAI 和 OpenRouter等供应商API

爆：GitHub Copilot支持包括Anthropic、Azure、Google Gemini、Groq、OpenAI 和 OpenRouter等供应商APIJetBrains和Xcode现已支持自带API密钥(BYOK)使用GitHub Copilot Chat，支持Anthropic、Azure等主流AI提供商。用户可灵活选择模型，享受更好的控制和实验体验。安装最新插件…...

编程日记 2025/9/17 13:13:10

JavaWeb05 - 详解

JavaWeb05 - 详解pre { white-space: pre !important; word-wrap: normal !important; overflow-x: auto !important; display: block !important; font-family: "Consolas", "Monaco", "Courier New", monospace !important; font-size: 14px !…...

编程日记 2025/9/17 15:18:24

CF182C

根据贪心策略，应当选择 \(k\) 个最小的负数改为正数，或选择 \(k\) 个最大的正数改为负数，才可能使答案最大。那么可以先把数按正负分开，并确定每个数在同符号数中的排名。建立权值线段树，记录每个数出现的次数、单个数大小、总贡献和，查询时类似线段树二分，如果数值较大…...

编程日记 2025/9/15 19:52:25

CF185D

大胆猜测，所有数的最大公约数一定很小：偶数时为 \(1\)，奇数时为 \(2\)。设两个正整数 \(n,m\) 且 \(n<m\)，最大公约数 \(\gcd(k^{2^n}+1,k^{2^m}+1)=d\)，则有 \(k^{2^n}\equiv k^{2^m} \equiv -1\pmod d,k^{2^{n+1}} \equiv (k^{2^{n+1}})^{\frac{2^m}{2^{n+1}}} \equi…...

编程日记 2025/9/15 19:52:19

Python计算文件md5

Python计算文件md5 基础版本1 import hashlib2 3 def calculate_md5(file_path, chunk_size=8192):4 """5 计算大文件的MD5值6 7 Args:8 file_path (str): 文件路径9 chunk_size (int): 每次读取的字节数，默认8KB 10 11 …...

编程日记 2025/9/15 19:52:14

CF201C

最优的方案应该是先往一个方向走，然后走回来，再往另一个方向走不回来。考虑用 dp 模拟这个过程。设 \(f_{i,0/1}\) 表示从第 \(i\) 个点出发往左走，不一定/一定回到 \(i\) 号点的最大次数，则有转移： \[\begin{array}{l} f_{i,1}=f_{i-1,1}+a_{i-1}-[2 \nmid a_{i-1}]\\f_{…...

编程日记 2025/9/17 14:16:59

CF1774D

首先 \(1\) 的总个数不能被 \(n\) 整除时无解。 否则一定有解（因为每一列上的 \(1\) 的位置都可以随意变动，故实际上相当于可以随便放）。为了步数最少，一定是用缺少 \(1\) 行的 \(0\) 与过多 \(1\) 行的 \(1\) 交换，这样能同时使两行更接近答案。实现时先枚举列，再根据每…...

编程日记 2025/9/15 19:52:02

CF23C

挺神奇的思维题。 首先将所有元素按 \(a\) 从大到小排序，考虑交叉选，即要么 \(a_1,a_3,a_5,\cdots,a_{2n-1}\)，要么 \(a_1,a_2,a_4,\cdots,a_{2n-2}\)。无论选哪种，\(a\) 一定满足要求（前者 \(a_1>a_2,a_3>a_4,\cdots,a_{2n-3}>a_{2n-2}\)，各式相加即可，后者 \…...

编程日记 2025/9/16 13:37:01

CF37C

将每个 01 串看作一个二进制数，将长度从小到大排序，对于当前第 \(i\) 个串，首先在第 \(i-1\) 个串的基础上加 \(1\)（如果不能加 \(1\) 即爆位数则无解），如果长度相同则无需任何操作，否则按照缺少的长度从后面补 \(0\)。这样做能保证长度短的不为长度长的前缀，且尽可能的…...

编程日记 2025/9/16 13:37:00