动态规划中状态与含义的适当转换

· · 算法·理论

例题：AT_dp_e。

正常的背包中我们记 f_{i, j} = k 表示前 i 个物品，重量和为 j，价值和为最大为 k。然而，这题中 j 可以非常大然而 k 充分小，将 k 放在含义中显得非常浪费。考虑将较小的 k 放在状态中， 把 j 放到含义中。我们称 f_{i, k} = j 表示前 i 个物品，价值和恰为 k，重量和最小为 j。转移与原本的状态类似，f_{i, k} = \min\{f_{i - 1, k}, f_{i - 1, k - v_i} + w_i\}。求答案时从大到小枚举 k，如果 f_{n, k} \leq W 直接输出即可。

#include<bits/stdc++.h>
#define mem(a, v) memset(a, v, sizeof(a))

using namespace std;

const int maxn = 100 + 10, maxv = 1e3;

int n, m;
int a[maxn], b[maxn], f[maxn * maxv];

int main(){
    scanf("%d %d", &n, &m);
    for (int i = 1; i <= n; i++){
        scanf("%d %d", &a[i], &b[i]);
    }
    mem(f, 0x3f), f[0] = 0;
    for (int i = 1; i <= n; i++){
        for (int j = i * maxv; j >= b[i]; j--){
            f[j] = min(f[j], f[j - b[i]] + a[i] <= m ? f[j - b[i]] + a[i] : m + 1);
        }
    }
    for (int i = n * maxv; ~i; i--){
        if (f[i] <= m){
            printf("%d", i);
            return 0;
        }
    }

return 0;
}

通过上面的例子，我们发现可以将 DP 中的所有状态和含义放进一个集合（如上文中是 \{i, j, k\}）。状态的大小是受到时空限制的，但是含义大小不受限制。我们可以考虑选择集合中的一个元作为含义，剩下元的作为状态。当我们选取 k 作为含义时状态过大，我们就应该改选 j 作为含义，此时状态便足够小了。

应用：Union2024 S1178。

f(x) = f(0) + \sum_{i = 1}^{x} [i \notin S] = \sum_{i = 1}^{x} [i \notin S] = x - \sum_{i = 1}^{x} [i \in S]

题目允许将 n 分为 k 段，实际上就是找到一个 \{a_i\} \in \mathbb{N}^k, \sum a_i = n，使得

\begin{aligned} \sum f(a_i) &= \sum_{i = 1}^{k} (a_i - \sum_{j = 1}^{a_i} [j \in S])\\ &= \sum_{i = 1}^{k} a_i - \sum \sum_{j = 1}^{a_i} [j \in S]\\ &= n - \sum_{i = 1}^{k} \sum_{j = 1}^{a_i} [j \in S]\\ \end{aligned}

取得最小值，即

\sum_{i = 1}^{k} \sum_{j = 1}^{a_i} [j \in S]

取得最大值。

设 f_{i, j} = p 表示在至多分为 i 段，总长为 j 时上式的最大值为 p。j 与 n 同阶，为 10^9，状态显然过大。然而 p 与 km 同阶，为 10^4。考虑改设 f_{i, p} = j 表示在至多分为 i 段，上式的值恰为 p 时最小的总长 j。转移是简单的

f_{i, p} = \min_{j = 0}^{\min\{k, m\}} \{f_{i - 1, p - j} + a_j\}

我们注意到 f_{i, j} 随 j 上升而单调不降，这是因为如果使上式的值达到 p 仅需要 f_{i, p} 的总长，那么如果 p' < p，我们只需要在 f_{i, p} 的基础上删除一些点即可，一定小于等于 f_{i, p}。于是我们在求答案时二分最大的 l 使得 f_{k, l} \leq n 即可。时间复杂度 \mathcal{O}(k^2m + q\log(km))。

#include<bits/stdc++.h>
#define mem(a, v) memset(a, v, sizeof(a))

using namespace std;

const int maxm = 100 + 10, maxk = 100;

int m, q;
int a[maxm];
long long f[maxk + 10][maxk * maxm];

int main(){
    freopen("run.in", "r", stdin);
    freopen("run.out", "w", stdout);
    scanf("%d", &m);
    for (int i = 1; i <= m; i++){
        scanf("%d", &a[i]);
    }
    sort(a + 1, a + m + 1);
    mem(f, 0x3f), f[0][0] = 0;
    for (int i = 1; i <= maxk; i++){
        for (int j = 0; j <= i * m; j++){
            for (int k = 0; k <= m && k <= j; k++){
                f[i][j] = min(f[i][j], f[i - 1][j - k] + a[k]);
            }
        }
    }
    scanf("%d", &q);
    while (q--){
        int n, k;
        scanf("%d %d", &n, &k);
        int l = 0, r = k * m;
        while (l < r){
            const int mid = l + r + 1 >> 1;
            if (f[k][mid] <= n){
                l = mid;
            }else{
                r = mid - 1;
            }
        }
        printf("%d\n", n - l);
    }

return 0;
}