算法小站
首页
wiki
新鲜事
文章搜索
网站导航
回忆录
首页
wiki
新鲜事
文章搜索
网站导航
回忆录
登录
注册
算法基础
搜索
数据结构
字符串
数学
图论
动态规划
计算几何
杂项
wiki 主题
算法基础
二维偏序
高维前缀和
树上差分
中位数定理
搜索
数据结构
线段树
线段树单点修改
线段树区间修改
动态开点线段树
线段树的合并(一)
可持久化线段树
树链剖分
平衡树
FHQ-Treap
珂朵莉树
分块
位分块
根号分治
虚树
字符串
回文串
回文树
数学
组合计数
二项式定理
生成函数(一)
FFT
多项式与形式幂级数
同余与模
同余与模的应用
同余与模的概念
特殊的数
斯特林数
斯特林数相关的恒等式
斯特林数的综合应用
FFT的应用
整除分块
图论
图的连通性
有向图的强连通分量
无向图的割点割边和双连通分量
流和匹配
最大流
最大流的一些应用
最小割
费用流
图论杂项
最大团搜索算法
树上问题
kruskal重构树
kruskal重构树的一些问题
最短路
差分约束
动态规划
背包模型
dp优化
凸壳优化
单调队列优化
计算几何
凸包(一)
杂项
启发式合并
高精度
一些经典问题
约瑟夫环
曼哈顿距离
多重集合的排列组合
蔡勒公式
排列与置换
Catalan数与格路径
主题名称
是否为父主题
是否为其添加wiki文章
取 消
确 定
选择主题
修改主题名称
修改父主题
修改wiki文章
取 消
删 除
修 改
算法基础
搜索
数据结构
字符串
数学
图论
动态规划
计算几何
杂项
计算几何
凸包(一)
[[ item.c ]]
0
0
凸优化(一)
## (min, +) 卷积 闵可夫斯基和的定义是,两个点集$$A, B$$的闵可夫斯基和是 ```math \displaystyle A + B = \{a + b \mid a \in A, b \in B\} ``` 对于函数$$g, h$$对应的点集,它们的闵可夫斯基和生成新的点集,下凸包对应的函数$$f$$ 恰好是$$g, h$$的 **(min, +)** 卷积 ```math \displaystyle f(i) = \min_{j + k = i} \{g(j) + h(k)\} ``` > 通用算法 **凸性** 如果$$g, h$$都是**下凸的**,那么等价于求它们对应点集的**闵可夫斯基和的下凸包**  **差分贪心** > 构造差分数组 对于$$f(i) = \min\_{j+k=i} (g(j) + h(k))$$,求$$g, h$$的差分数组 分别是$$\Delta g(1) \leqslant \Delta g(2) \leqslant \cdots, \Delta h(1) \leqslant \Delta h(2) \leqslant \cdots$$ (其中,$$\Delta g(i) = g(i) - g(i-1)$$) > 构造起始点和递推 起始点:$$f(0) = g(0) + h(0)$$ 考虑递推,$$f(i-1) \to f(i)$$,不难发现,此时 ```math \displaystyle f(i) = f(i-1) + \min_{j+k = i} \{\Delta g(j) , \Delta h(k) \} ``` (说人话就是,$$i$$想要增长`1`,要么从$$g$$中$$j-1 \to j$$中增长,要么从$$h$$中$$k-1 \to k$$中增长) 这是什么?这是**对差分数组归并** > 对差分数组归并 归并差分数组,$$\textbf{merge}(\Delta g, \Delta h) \to c$$ 我们得到$$c_1 \leqslant c_2 \leqslant c_3 \leqslant \cdots$$,我们有 ```math \displaystyle f(1) = f(0) + c_1, f(2) = f(1) + c_2, \cdots \\ \Longrightarrow f(i) = f(0) + \sum_{k = 1}^{i} c_k ``` ### 差分贪心 **资源分配问题** 假设对$$i$$个数操作$$j$$次,获取的最小代价定义为$$dp(i, j)$$ 考虑**操作增量**$$j - j^{\*} = c$$,那么状态转移方程可以写成 ```math \displaystyle dp(i, j) = \min_{0 \leqslant c \leqslant j} \{ dp(i-1, j-c) + f_i(c) \} ``` 如果对于**确定的**$$i$$来说,$$f_i(c)$$是关于$$c$$的**离散下凸函数**,这个`dp`就完全退化成贪心 可以有如下算法 1)确定基准值(初始状态),$$base = \sum\_{i = 1}^{n} f\_i(0)$$ 2)定义差分值(边际变化),令$$\Delta_i(c) = f_i(c-1) - f_i(c)$$ (求最小值问题,实际上对应每次差分**损失最大**) 因为$$f\_i(c)$$具有凸性,所以对$$\Delta f_i(c)$$进行排序,$$\Delta f_i(1) \ge \Delta f_i(2) \ge \dots \ge \Delta f_i(m)$$ 3)全局贪心,假设说我们最多可以操作$$k$$次,那么最终的答案是 ```math \displaystyle ans = base - \sum_{x = 1}^{k} (\text{排序后的第 } x \text{ 个 } \Delta) ``` ### 差分贪心数学证明 > 构造差分数组 对于状态转移方程 $$dp(i, j) = \min\_{0 \le c \le j} \{ dp(i-1, j-c) + g\_i(c) \}$$ 写成 **(min, +)** 卷积,$$dp\_i = dp\_{i-1} \oplus g\_i$$ 假设说$$dp(i, j-1)$$我们已经求出来了,那么 ```math dp(i, j-1) = dp(i-1, x^*) + g_i(y^*) \quad (\text{其中 } x^* + y^* = j-1) ``` 现在考虑从$$dp(i, j-1) \to dp(i, j)$$,要么这`1`次多出来的用$$dp(x^\*)$$贡献,要么用$$g(y^\*)$$贡献 ```math \displaystyle dp(i, j) = dp(i, j-1) + \min\{\Delta dp_{i-1}(x^* + 1), \Delta g_i(y^* + 1)\} ``` 这意味着$$\Delta dp\_i(j) = \min\\{ \Delta dp\_{i-1}(x^\*+1), \Delta g\_i(y^\*+1) \\}$$ 最终的答案 ```math \displaystyle dp(n, k) = dp(n, 0) + \sum_{x = 1}^{k} \Delta dp_n(x) ``` > 现在问题来了,$$\Delta dp\_{i-1}(x^\*+1)$$ 数组怎么求? 关于$$\Delta dp$$的递推,之前已经知道 ```math \Delta dp_i(j) = \min \{ \Delta dp_{i-1}(x^* + 1), \Delta g_i(y^* + 1) \} ``` 那么从$$n = 2$$开始,不难发现$$\Delta dp_2(j) = \min (\Delta dp_1(x^\*+1), \Delta g_2(y^\* + 1))$$ 而$$dp_1 = 0 + g_1$$,所以$$dp_2(j) = \min(\Delta g_1(x^\* + 1), \Delta g_2(y^\* + 1))$$ 说明$$dp_2$$的每一个增量,要么是来自$$g_1$$的某一个差分,要么是来自$$g_2$$的某个差分 因为取`min`,所以取差分最小的,从小到大依次挑选 由此,$$\Delta dp_2$$的集合是$$\text{Sort}(\Delta g_1 \cup \Delta g_2)$$ **递推到 n**,我们有 ```math \Delta dp_n = \text{sort}(\Delta g_1 \cup \Delta g_2 \cup \cdots \cup \Delta g_n) ``` > 算法 1)一开始令$$dpv = dp(n, 0)$$ 而根据$$dp(i, 0) = dp(i-1, 0) + g\_i(0)$$可以得到,$$dpv = dp(n, 0) = \sum_i g_i(0)$$ 2)对于每个$$i$$,预处理出每个$$(i, y)$$所对应的**差分**$$\Delta g_i(y) = g_i(y) - g_i(y-1)$$ 然后对$$\Delta g_i(y)$$排序 3)最后得出 ```math res = dpv + \sum_{x = 1}^{k} \Delta dp_n(x) \\ = dpv + \sum_{j = 1}^{k} (\Delta g \text{ 排序后的数组第 } j \text{ 个数}) ``` ### E. Kevin and And **[E. Kevin and And](https://codeforces.com/contest/2061/problem/E)** 给定一个长度为`n`的序列`a[1...n]`和长度为`m`的序列`b[1...m]`,其中$$m \leqslant 10$$ 最多允许执行`K`次操作,`K`是给定的,每次操作你自己任意选择$$(i, j)$$,令`a[i] &= b[j]` 问`K`次操作结束后,`a`序列最小的和是多少? **算法分析** 首先可以预处理,暴力打表,`table(i, c)`表示对$$a_i$$应用$$c$$次操作,能够得到最小的数是多少 然后可以写出一个朴素的`dp`方程,$$dp(i, j)$$表示对前$$i$$个数,总共应用了$$j$$次操作 能够得到最小的和 枚举我们在$$a_i$$身上浪费的$$c$$次操作,可以得到转移方程 ```math dp(i, j) = \min\{ dp(i-1, j-c) + table(i, c) \} ``` 注意到$$table_i(c)$$关于$$c$$是单调递减的(`AND` 操作的性质,每次移去一个最高位), 所以,$$c$$越大$$table_i$$反而越小,$$table$$**是下凸的**,这样就可以用**差分贪心**了 具体来说,就是令$$sum_0 = \sum_i table_i(0)$$,然后对$$\Delta table_i(c) = table_i(c) - table_i(c-1)$$排序 最后我们的$$\Delta dp_n[\*] = \text{Sort}(\Delta table_1, \Delta table_2, \cdots)$$ ```math sum_0 - \sum_{i = 1}^{k} \Delta table_i = sum_0 - \text{前 } k \text{ 大的和} ``` 就是答案 ```bash void solve(int cas) { int n, m, K; cin >> n >> m >> K; vector<i64> a(n, 0), b(m, 0); for (int i = 0; i < n; i++) cin >> a[i]; for (int i = 0; i < m; i++) cin >> b[i]; // table(i, 0) = a[i], must!! vector table(n+5, vector<i64>(m+5, inf<i64>)); for (int i = 0; i < n; i++) table[i][0] = a[i]; vector<i64> asum((1 << m) + 5, 0); auto getsum = [&]() -> void { for (int mask = 1; mask < (1 << m); mask++) { i64 res = -1; for (int j = 0; j < LOG; j++) if (mask >> j & 1) { res == -1 ? res = b[j] : (res = res & b[j]); } asum[mask] = res; } }; getsum(); // debug(asum); for (int i = 0; i < n; i++) { for (int mask = 1; mask < (1 << m); mask++) { auto j = popcnt(mask); chmin(table[i][j], a[i] & asum[mask]); } } vector<i64> slope; for (int i = 0; i < n; i++) { const auto &g = table[i]; for (int j = 1; j <= m; j++) { slope.emplace_back(llabs(g[j] - g[j-1])); } } // debug(slope); sort(slope.begin(), slope.end(), greater<>()); i64 ans = accumulate(a.begin(), a.end(), 0LL); for (int i = 0; i < K; i++) ans -= slope[i]; cout << ans << "\n"; } ``` ## dp 斜率优化 一般在`dp`方程中,会给定若干个点,$$(x_1, y_1), (x_2, y_2), \cdots (x_k, y_k)$$ 然后给定$$(a, b)$$,要求$$\max_i (ax_i + by_i)$$ 特殊的情况求$$y_i - kx_i$$,这实际上对应$$(a, b) = (-k, 1)$$的特殊情况  ### 玩具装箱 **[玩具装箱](https://www.luogu.com.cn/problem/P3195)** 有`n`件玩具,`C[1...n]`,然后编号`[i...j]`玩具装箱,装箱后长度是$$x = (\sum C\_{k = i}^{j}) + (j - i)$$ 然后这一段的代价是$$(x - L)^2$$,其中$$L$$给定,最小化这个总代价 **算法分析** 首先,这个问题要求$$[i, j)$$中每个元素的$$C \leftarrow C+1$$,可以怎么处理呢? 可以让$$[i, j]$$区间内的每个$$C$$都`+= 1`,然后`L += 1` 这样区间的代价就是$$(\sum C - L)^2$$,然后再求一遍前缀和,这样 ```math \displaystyle dp_i = \min_{0 \leqslant j < i} (dp_j + (S_i - S_j - L)^2) ``` 斜率优化的项,一般有三部分组成`j 相关,i * j,i 相关` 这里令$$S_i^\* = S_i - L$$,那么就有 ```math \displaystyle dp_i = \min_{0 \leqslant j < i} (dp_j + S_j^2 - 2S_i^* S_j) + (S_i^*)^2 ``` > 斜率优化 令$$Y_j = dp_j + S_j^2, X_j = S_j$$,那么$$k = -2S_i^\*$$,考虑点$$P_j = (S_j, dp_j + S_j^2)$$ 对每个点$$i$$,查询$$\min\\{ Y_j - ki \cdot X_j \\}$$ 做法的框架如下,**维护下凸壳** ```math \displaystyle dp_i = \min(\text{下凸壳}) + (S_i^*)^2 ``` 然后将$$P_i$$插入到下凸壳中 维护下凸壳比较难,涉及到动态凸包 但注意到这个问题中,点$$(S_j, dp_j + S_j^2)$$,斜率$$|k| = (2S_i^\*)^2$$,二者都是单调递增的 首先,$$S_j$$递增,保证了每次插入凸壳的点都只会在右边 斜率$$|k|$$递增,保证了直线是会一直保持往右移动的趋势的  > 算法实现 ```bash // 玩具装箱,dp(i) = min{ dp(j)+S(j)*S(j) - 2S(i)S(j) } + S(i)*S(i) void solve(int cas) { int n; i64 L; cin >> n >> L; L += 1; vector<i64> S(n+1, 0); for (int i = 1; i <= n; i++) { i64 c; cin >> c; S[i] = S[i-1] + c + 1; } vector<i64> dp(n+5, 0); auto getK = [&](int i) -> i128 { return (i128)(S[i] - L) * 2; }; auto Y = [&](int j) -> i128 { return (i128)dp[j] + (i128)S[j] * S[j]; }; auto X = [&](int j) -> i128 { return (i128)S[j]; }; deque<int> que; que.push_back(0); for (int i = 1; i <= n; i++) { i64 ki = getK(i); // min,队列中,有用的斜率单调递减 while (que.size() >= 2) { auto j1 = que[0], j2 = que[1]; if ( (Y(j2)-Y(j1)) <= (i128)ki * (X(j2)-X(j1)) ) que.pop_front(); else break; } // 斜率最大的就是队首 auto j = que.front(); dp[i] = Y(j) - ki * X(j) + (S[i]-L) * (S[i]-L); // 插入 i,维护下凸壳 while (que.size() >= 2) { auto j2 = que.back(), j1 = que[que.size() - 2]; if ( (Y(i)-Y(j2)) * (X(j2)-X(j1)) <= (Y(j2)-Y(j1)) * (X(i)-X(j2)) ) que.pop_back(); else break; } que.push_back(i); } cout << dp[n] << "\n"; } ``` ### Land Acquisition G **[USACO08MAR Land Acquisition G](https://www.luogu.com.cn/problem/P2900)** 农夫准备扩大他的农场,正在考虑购买$$n$$块长方形土地 他可以并购一些土地,比如并购$$3 \times 5, 5 \times 3$$,他需要付`max(长) * max(宽)` 这个例子中,他要付$$5 \times 5$$美元 现在需要计算他买下所有土地所需要的最小费用 **算法分析**  > 特别说明,斜率优化一般最开始要加入哨兵节点`0`,$$(X_0, Y_0) = (0, 0)$$ ```bash void solve(int cas) { int n; cin >> n; using pr = pair<i64, i64>; vector<pr> a(n+1); for (int i = 1; i <= n; i++) { // auto &[x, y] = a[i]; cin >> a[i].first >> a[i].second; } // debug(a); sort(a.begin()+1, a.end()); vector<pr> cand; cand.emplace_back(0, 0); i64 last = 0; for (int i = n; i >= 1; i--) { // auto [xi, yi] = a[i]; auto xi = a[i].first, yi = a[i].second; if (yi <= last) continue; cand.emplace_back(xi, yi); last = yi; } reverse(cand.begin()+1, cand.end()); // debug(cand); vector<i64> dp(n+5, 0); auto getK = [&](int i) -> i128 { // auto [xi, yi] = cand[i]; auto xi = cand[i].first; return (i128)(xi); }; auto Y = [&](int j) -> i128 { return (i128)dp[j]; }; auto X = [&](int j) -> i128 { // auto [_, yj] = cand[j+1]; auto yj = cand[j+1].second; return (i128)(-yj); }; deque<int> que; que.push_back(0); auto m = cand.size(); for (int i = 1; i < cand.size(); i++) { i64 ki = getK(i); while (que.size() >= 2) { auto j1 = que[0], j2 = que[1]; if ( (Y(j2)-Y(j1)) <= (i128)ki * (X(j2)-X(j1)) ) que.pop_front(); else break; } auto j = que.front(); dp[i] = Y(j) - ki * X(j); if (i == cand.size() - 1) break; while (que.size() >= 2) { auto j2 = que.back(), j1 = que[que.size() - 2]; if ( (Y(i)-Y(j2)) * (X(j2)-X(j1)) <= (Y(j2)-Y(j1)) * (X(i)-X(j2)) ) que.pop_back(); else break; } que.push_back(i); } cout << dp[m - 1] << "\n"; } ```
看完文章有啥想法
发布评论
目录
[[ item.c ]]
13 人参与,0 条评论