wiki - 算法小站

wiki 主题

主题名称

是否为父主题

是否为其添加wiki文章

选择主题

修改主题名称

修改父主题

修改wiki文章

算法基础搜索数据结构字符串数学图论动态规划计算几何杂项

计算几何

凸包（一）

[[ item.c ]]

凸优化（一）

## (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$$都是**下凸的**，那么等价于求它们对应点集的**闵可夫斯基和的下凸包**
![](/media/content_img/hull-01.png)

**差分贪心**
> 构造差分数组

对于$$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)$$的特殊情况
![](/media/content_img/hull-02.png)

### 玩具装箱
**[玩具装箱](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|$$递增，保证了直线是会一直保持往右移动的趋势的
![](/media/content_img/slope-dp.png)

> 算法实现

```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$$美元
现在需要计算他买下所有土地所需要的最小费用

**算法分析**
![](/media/content_img/slope-dp2.png)

> 特别说明，斜率优化一般最开始要加入哨兵节点`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";
}
```

看完文章有啥想法

算法小站

wiki 主题

计算几何

凸优化（一）

目录