NCC-79601 Captain's Log

NCC-79601 Captain's Log

To boldly go where no one has gone before.

【复习笔记】Week 3 动态规划

posted on 2019-11-02 22:27:23 | under 复习笔记 |

DAY 1

以下用 $w[i]$表示重量 / 体积, $v[i]$表示价值。

01 背包

$$f[i][j]=\max\{f[i-1][j-w[i]]+v[i]\}$$ 当然,在没有限制的情况下也可以把第一维滚掉: $$f[j]=\max\{f[j-w[i]]+v[i]\}$$ 在这种情况下,需要倒序枚举 $j$的值。

满背包问题

如果题目要求把背包装满,则可以把所有 $f[i]$设为 $-\infty$,表示背包体积为 $f[i]$时无解;然后令 $f[0]=0$,再进行转移。每次转移时判断前驱状态 $f[j-w[i]]$是否有解,只在有解的情况下发生转移。

多重背包

二进制拆分法

把物品个数 $c[i]$二进制拆分,比如: $c[i]=13$,则拆分为 $1,2,4$倍的物品,即可表示 $[0,7]$范围内的所有数;再拆分一个 $13-7=6$倍的物品,即可表示 $[6,13]$范围内的所有数,因此 $[0,13]$内所有的数都得到表示,且拆分出来的物品的和不会超过 $c[i]$倍。

单调队列优化

可以考虑到,既然每个物品都有确定的体积,那么在转移的时候,一种状态 $f[j]$的值只与 下标和 $j$对 $w[i]$余数相同 的状态相关,那么可以考虑节省掉多余的一些枚举。

首先写出朴素转移方程: $f[i][j]=\max\{f[i-1][j-k\cdot w[i]]+k\cdot v[i]\}$,很显然 $f[i][\cdots]$只与 $f[i-1][\cdots]$相关,因此可以把第一维滚动掉,设滚动数组为 $g[i]$;设一个决策 $k$比当前决策 $k_0$更优,则有:

$$g[j-k\cdot w[i]]+k\cdot v[i]>g[j-k_0\cdot w[i]]+k_0\cdot v[i]$$ $$\Rightarrow g[j-k\cdot w[i]]-g[j-k_0\cdot w[i]]>v[i]\cdot(k_0-k)$$ 由于 $j-k\cdot w[i]\equiv j-k_0\cdot w[i](\mod w[i])$,所以每次枚举余数相同的 $j$即可;而对于这个不等式,可以想到用 单调队列 来维护,具体为:先把不合要求(选了超过 $c[i]$个数)的状态出队,然后通过上面的不等式维护弹掉队尾,将当前状态装入单调队列之后,再进行决策。这几步的顺序差异会导致答案出错,具体只能感性理解。

// https://www.luogu.org/problem/P1776
#include <bits/stdc++.h>
using namespace std;
const int MAXW = 4e4 + 10;
int n, m, f[MAXW], g[MAXW];
int q[MAXW], head, tail, ans = 0;

int main() {
    scanf("%d %d", &n, &m);
    for (int i = 1, v, w, c; i <= n; i++) {
        scanf("%d %d %d", &v, &w, &c);
        if (w == 0) {
            ans += v * c;
            continue;
        }
        // 防止出现除以 0 的情况
        c = min(c, m / w);
        for (int r = 0; r < w; r++) {
            // 先枚举余数
            head = 1, tail = 0;
            // 记得情况队列
            for (int j = r; j <= m; j += w) {
                // 同余枚举
                while (head <= tail && (j - q[head]) / w > c)
                    head++;
                while (head <= tail && g[j] - g[q[tail]] > (j - q[tail]) / w * v)
                    tail--;
                // j 比 q[tail] 更优,则直接出队
                // 先把单调队列维护好了再来决策
                q[++tail] = j;
                f[j] = g[q[head]] + (j - q[head]) / w * v;
            }
        }
        memcpy(g, f, sizeof(g));
    }
    int ans = 0;
    for (int i = 1; i <= m; i++)
        ans = max(ans, f[i]);
    printf("%d\n", ans);
    return 0;
}

完全背包

把 01 背包中 $j$的枚举顺序由倒序改为顺序即可。

处理多重背包型方案数问题的时候,用二进制拆分可能会非常困难。此时可以用上完全背包,每次转移后减去不合法的方案数。

分组背包

分组背包的 枚举顺序 极其重要,枚举顺序为:组数 $\rightarrow$体积 $\rightarrow$物品。

体积的枚举放在物品前的原因:每个组内只能选一个物品。

可以这样记忆:对于每个组都做一次单个物品的 01 背包,那么就可以保证每个组仅选择一个物品。

for (int k = 1; k <= tot; k++)
    for (int i = m; i; i--)
        for (int j = 1; j <= c[k]; j++)
            if (i >= w[k][j])
                f[i] = max(f[i], f[i - w[k][j]] + v[k][j]);

树形背包

树形背包的转移方程和 01 背包是类似的。设 $f[u][j]$表示以 $u$为根的子树容积为 $j$时的最大价值,则可得:

$$f[u][j]=\max_{k=0}^{j}\{f[u][j-k]+f[v][k]\}$$

与背包相同,此处的 $j$的枚举顺序也是倒序的。

// https://www.luogu.org/problem/P2014
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 3e3 + 10;
struct sidetable {
    int to, next;
} edge[MAXN];
int head[MAXN], id = 0;
int n, m, a[MAXN], f[MAXN][MAXN];

void build_edge(int u, int v) {
    edge[++id].to = v;
    edge[id].next = head[u];
    head[u] = id;
    return ;
}

void dfs(int u) {
    f[u][1] = a[u];
    for (int i = head[u]; i; i = edge[i].next) {
        int v = edge[i].to;
        dfs(v);
        for (int j = m; j; j--)
            for (int k = 1; k < j; k++)
                f[u][j] = max(f[u][j], f[u][j - k] + f[v][k]);
    }
    return ;
}

int main() {
    scanf("%d %d", &n, &m);
    m++;
    // 0 号点是怎么都要选的
    for (int i = 1, pre; i <= n; i++) {
        scanf("%d %d", &pre, &a[i]);
        build_edge(pre, i);
    }
    dfs(0);
    printf("%d", f[0][m]);
    return 0;
}

一个改进

可以看出上面的算法复杂度达到了 $O(n^3)$级别,当然是很可能爆掉。可以发现第二、三层循环考虑了很多本来不需要考虑到的情况,因此可以用子树的 size[] 来优化枚举。在这种情况下,一个点对 $(u,v)$共同出现在转移中的条件是更新到它们的 LCA,因此任意点对都只会出现一次,总复杂度即 $O(n^2)$。这也是对冗余转移的优化。

void dfs(int u) {
    size[u] = 1;
    f[u][1] = a[u];
    for (int i = head[u]; i; i = edge[i].next) {
        int v = edge[i].to;
        dfs(v);
        size[u] += size[v];
        for (int j = size[u]; j; j--)
            for (int k = 1; k <= min(j - 1, size[v]); k++)
                // 第二层是 size[u],第三层是 min(j - 1, size[v])
                f[u][j] = max(f[u][j], f[u][j - k] + f[v][k]);
    }
    return ;
}

求方案数

把求最值改为求和即可,注意要把 $f[0]$设为 $1$。

输出方案

可以在 dp 过程中就记录一个 $g[i][j]$表示物品 $i$在背包容积为 $j$的时候是否被选中。因为最后一件物品存储的是最终状态,所以从最后一件物品进行循环;然后按照下面的伪代码执行:

int v = V;  //记录当前的存储空间
for (从最后一件循环至第一件) {
    if (g[i][v]) {
        选了第 i 项物品;
        v -= 第 i 项物品的价值;
    } else {
        未选第 i 项物品;
    }
}

DAY 2

树形 dp

树上路径问题

一般这种问题会用到点分治,然而我没有学点分治,因此只能用树形 dp 去解决。

例题:一棵树,1 号点为根,树上每个节点对应一个值 $k[i]$。初始的时候所有点都是白色的。每次操作选择一个节点 $i$, $i$必须是白色的,然后 $i$到根的链上(包括节点i与根)所有与节点 $i$距离小于 $k[i]$的点都会变黑,已经是黑的点保持为黑。问最少使用几次操作能把整棵树变黑。

分析:维护 $f[u][0/1]$,其中 $f[u][0]$表示 $u$子树中的上次覆盖最远还能覆盖多少个点(不选), $f[u][1]$表示从 $u$子树中上次覆盖开始再覆盖一个点最远能够覆盖多少个点(选)。

// https://ac.nowcoder.com/acm/problem/13249
void dfs(int u) {
    f[u][1] = k[u], f[u][0] = 0;
    for (unsigned int i = 0; i < G[u].size(); i++) {
        int v = G[u][i];
        dfs(v);
        f[u][0] = max(f[u][0], f[v][0] - 1);
        f[u][1] = max(f[u][1], f[v][1] - 1);
    }
    if (!f[u][0]) {
        // 无法覆盖到此处,必须重新开始覆盖
        ans++;
        f[u][0] = f[u][1];
        f[u][1] = 0;
        // u 的父亲不能继承 f[u][1] 的状态
    }
    return;
}

树上点对距离和问题

若给一棵树,询问所有点对 $(u,v)$中 $u\rightarrow v$的路径长度之和,很容易想到的做法是双重 for 循环枚举点对,然后用 LCA 计算点对距离。但是这种做法的复杂度是 $O(n^2logn)$,即使用 RMQ 实现 $O(1)$的 LCA 也是 $O(n^2)$,当然是不够优秀的。

考虑用另一种思路处理这个问题:对于每一条边,只需要统计这条边的边权对于答案的贡献。设这条边连接的两点分别为 $u,v$(且满足 dep[u] < dep[v]),则这条边计入答案的次数就是 $u$及其以上部分子树大小 乘上 $v$的子树大小(乘法原理)。这样的复杂度为 $O(n)$,足够优秀。

变形: 设一棵树的所有点都是白色,从中选 $k$个节点染成黑色,问黑点的两两距离之和 与 白点的两两距离之和 的和的最大值。

分析:用 $f[i][j]$来表示 $i$的子树中选 $j$个点染成黑点能够对答案产生的最大贡献。用这种方式描述状态以后,就把问题转化为了 树上满背包 问题,当然写法和普通的满背包没什么区别。在统计贡献的时候,就可以用到上面提到的乘法原理结论了。

void dfs(int u, int fa) {
    size[u] = 1;
    for (int e = head[u]; e; e = edge[e].next) {
        int v = edge[e].to;
        if (v == fa)
            continue;
        dfs(v, u);
        size[u] += size[v];
    }
    memset(f[u], -1, sizeof(f[u]));
    f[u][0] = f[u][1] = 0;
    for (int e = head[u]; e; e = edge[e].next) {
        int v = edge[e].to;
        ll w = edge[e].w;
        if (v == fa)
            continue;
        for (int i = min(k, size[u]); ~i; i--)
            for (int j = 0; j <= min(i, size[v]); j++)
                if (~f[u][i - j]) {
                    ll ctrb = 1LL * j * (k - j) * w + 
                     1LL * (size[v] - j) * (n - k - size[v] + j) * w;
                    // 计算当前边的贡献
                    f[u][i] = max(f[u][i], f[u][i - j] + f[v][j] + ctrb);
                }
        // 子树大小优化后的满背包
    }
    return ;
}

树上最大独立集

例题:选出一些点使得任意两点互不相连(也就是最大独立集)。这个的做法并没有想的那么复杂,用 $f[i][0/1]$表示 $i$节点 不选 / 选 时以 $i$为根的子树的最大独立集,然后感性转移即可。

void dfs(int u, int fa) {
    f[u][1] = 1;
    for (unsigned int i = 0; i < G[u].size(); i++) {
        int v = G[u][i];
        if (v == fa)
            continue;
        dfs(v, u);
        f[u][1] += f[v][0];
        f[u][0] += max(f[v][0], f[v][1]);
    }
    return ;
}

还有些树形 dp 的状态比较多,在状态数组后面多加几个维度就可以了。

状态压缩

例题:给出 $n$个点, $m$条边,以及 $R$个要到达的目的地(保证 $n\leq200,R\leq15$),求经过所有目的地的最短路径长度。

分析:这道题难在状态描述。可以先用 Floyd 跑出所有最短路。首先很容易想到用 $f[i]$压缩表示目的地是否走过,然后就不知道该怎么转移了。这时可以在状态中添加一个维度变成 $f[i][j]$,表示目的地是否走过的情况为 $i$,而最后到达 $j$点时的最小路径长度。这样做以后,只需要枚举状态 $\rightarrow$枚举当前起点 $\rightarrow$枚举当前终点,然后进行转移。

// https://ac.nowcoder.com/acm/problem/16122
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 210;
const int MAXR = 16;
int n, m, R, dst[MAXR];
int dis[MAXN][MAXN];
int f[1 << MAXR][MAXR];

void floyd() {
    for (int k = 1; k <= n; k++)
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= n; j++)
                dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j]);
    return ;
}

int main() {
    memset(dis, 0x3f, sizeof(dis));
    memset(f, 0x3f, sizeof(f));
    scanf("%d %d %d", &n, &m, &R);
    for (int i = 1; i <= R; i++)
        scanf("%d", &dst[i]);
    for (int i = 1; i <= n; i++)
        dis[i][i] = 0;
    for (int i = 1, a, b, c; i <= m; i++) {
        scanf("%d %d %d", &a, &b, &c);
        dis[a][b] = dis[b][a] = min(dis[a][b], c);
    }
    floyd();
    for (int i = 1; i <= R; i++)
        f[1 << (i - 1)][i] = 0;
    for (int i = 1; i < (1 << R); i++)
        for (int j = 1; j <= R; j++)
            if (i & (1 << (j - 1)))
                for (int k = 1; k <= R; k++)
                    if (!(i & (1 << (k - 1))))
                        f[i | (1 << (k - 1))][k] = min(
                            f[i | (1 << (k - 1))][k],
                            f[i][j] + dis[dst[j]][dst[k]]
                        );
    int ans = 0x3f3f3f3f;
    for (int i = 1; i <= R; i++)
        ans = min(ans, f[(1 << R) - 1][i]);
    printf("%d", ans);
    return 0;
}

DAY 3

区间 dp

用 $f[i][j]$表示 $[i,j]$区间的情况。为了保证前驱状态已经获知,一般的枚举顺序为:区间长度 $\rightarrow$区间起点 $\rightarrow$计算得出区间终点。类似这样:

// https://www.luogu.org/problem/P1063
for (int len = 2; len <= n; len++)
    for (int i = 1; i <= (n << 1); i++) {
        int j = i + len - 1;
        for (int k = i; k < j; k++)
            f[i][j] = max(f[i][j], f[i][k] + f[k + 1][j] + calc(i, j, k));
    }

当然也可以附加一维变成 $f[i][j][0/1]$,表示考虑 $[i,j]$区间,并且处于左端点 / 右端点的情况。

前缀和优化

观察: $$f[i][j]=\sum_{k}^{s[j]-s[k-1]\leq lim}f[k][j-1]$$ 这个式子非常吓人,不过可以考虑分步优化。首先把 $j$滚动掉,然后考虑使用前缀和优化这个式子:计 $s[i][j]=\sum f[i][j]$,那么只要获知表达式中 $k$的起始点(可以预处理),就可以 $O(1)$地计算出 $f[i][j]$的值,同时动态维护下一次要调用到的前缀和。

// https://www.luogu.org/problem/P2511
int cur = 0;
for (int i = 1; i <= n; i++) {
    while (s[i] - s[cur] > lim)
        cur++;
    L[i] = cur;
}
// 隔板法,有些写法没有见过
for (int i = 0; i <= n; i++)
    sum[i][0] = 1;
for (int J = 1, j = 1; J <= m; J++, j ^= 1) {
    sum[0][j] = 0;
    for (int i = 1; i <= n; i++) {
        f[i][j] = sum[i - 1][j ^ 1] % mod;
        if (L[i] - 1 >= 0)
            f[i][j] = (f[i][j] - sum[L[i] - 1][j ^ 1] + mod) % mod;
        sum[i][j] = (sum[i - 1][j] + f[i][j]) % mod;
    }
    ans = (ans + f[n][j]) % mod;
}

最长单调子序列

一般是用贪心去做,即维护一个数组 $b[i]$,其末尾表示当前长度的最长单调子序列的末尾最大 / 最小是多少。每次得到一个数 $a[i]$,要么合法地接在 $b$数组的末尾;要么二分查找 $b$中的某个符合条件的值(用 upper_bound() 或者 lower_bound() 都有可能),然后把它替换掉。

当然还有树状数组写法。离散化以后,用 $f[i]$表示以 $i$结尾的最长单调子序列长度,考虑最朴素的转移方程: $$f[i]=\max^{j<i}\{f[j]\}+1$$ 其中 $\max\{f[j]\}$就可以用树状数组维护。

两种方法都是 $O(nlogn)$的复杂度。

DAY 4

对于一类需要优化的题目,写出状态转移方程以后,观察式子有没有关于 $i,j$的交叉项;有交叉项就使用斜率优化,没有交叉项就使用单调队列优化。

还有一种方法是假设一个决策比另一个决策优,推出单调队列需要维护的东西,然后再进行优化。

斜率优化

斜率优化的使用前提是:能够把状态转移方程写成形如 $b=y+k\cdot x$的形式,其中 $b,k$只与 $i$有关,而 $x,y$只与 $j$有关。得出式子以后,要想清楚单调队列究竟是维护上凸还是下凸;同时还要注意计算直线斜率的时候会不会遇到除以 $0$的情况(验斜不在)。

例题:把 $n$个数分成 $k$个集合,每次分割获得的分数是所分得的两个集合 各自总和 之积。求最大得分并输出方案。

分析:首先,设三个数为 $a,b,c$,则无论怎么分割,最后的得分都是 $ab+ac+bc$,这为使用斜率优化以及记录路径降低了难度。用 $s[i]$表示前缀和, $f[i][j]$表示前 $i$个数分成 $j$段的最大得分,则有朴素转移方程: $$f[i][j]=\max\{f[k][j-1]+s[k]\cdot(s[i]-s[k])\}$$ 滚动掉 $j$的维度,设 $g[i]=f[i][j-1]$,则: $$f[i]=\max\{g[j]+s[i]\cdot s[j]-s^2[j]\}$$ 忽略掉 $\max$,原式整理为: $$s^2[j]-g[j]=s[i]\cdot s[j]-f[i]$$ 也就是 $l:y=kx-b$的形式。这里是要求 $b$的最大值,也就是让 $l$最低,所以维护下凸即可。需要注意的是,调用函数会降低性能,所以不要写一堆 x(i)y(i) 什么的再来算 slope(i, j)

关于记录路径,用 pre[i][j] 表示 f[i][j]f[pre[i][j]][j-1] 转移而来,最后从 f[n][k] 开始倒序遍历。

// https://www.luogu.org/problem/P3648
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN = 1e5 + 10;
const int MAXK = 210;
int n, k, a[MAXN];
ll s[MAXN], f[MAXN][2];
int q[MAXN], head, tail, pre[MAXN][MAXK];

double slope(int a, int b, int j) {
    if (s[a] == s[b])
        return 1e18;
    // 注意验斜不在
    return 1.0 * (s[a] * s[a] - f[a][j] - s[b] * s[b] + f[b][j]) / (s[a] - s[b]);
}

int main() {
    scanf("%d %d", &n, &k);
    for (int i = 1; i <= n; i++)
        scanf("%d", &a[i]), s[i] = s[i - 1] + a[i];
    for (int J = 1, j = 1; J <= k; J++, j ^= 1) {
        head = tail = 0;
        q[head] = 0;
        for (int i = 1; i <= n; i++) {
            while (head < tail && slope(q[head], q[head + 1], j ^ 1) < s[i])
                head++;
            while (head < tail && slope(i, q[tail], j ^ 1) < slope(i, q[tail - 1], j ^ 1))
                tail--;
            f[i][j] = s[q[head]] * (s[i] - s[q[head]]) + f[q[head]][j ^ 1];
            pre[i][J] = q[head];
            // 记录路径
            q[++tail] = i;
        }
    }
    printf("%lld\n", f[n][k & 1]);
    for (int x = n, i = k; i; i--)
        x = pre[x][i], printf("%d ", x);
    return 0;
} 

注意一点:斜率优化中,由于斜率的计算需要用到 $f[i]$的值,所以应该要先计算 $f[i]$,再把 $i$扔进单调队列中,否则斜率的计算就会出问题。

费用提前

如果发现 $f[i][j]$需要滚动才能使用斜率优化,并且式子中出现了与 $j$有关的项阻碍对式子的整理,那么就可以把与 $j$的项通过后缀思想转化为与 $j$无关的项。

例题:任务完成(费用 $=$完成时刻 $\times$费用系数)

分析:用 $f[i][j]$表示前 $i$个任务分成 $j$次完成的最小用时,朴素的转移方程为: $$f[i][j]=\min\{f[k][j-1]+(j\cdot S+st[i])\cdot(sf[i]-sf[k])\}$$ 然后考虑在一个点多启动一次机器,则会使费用增加 $S\times\sum$后面的费用系数。因此把这个费用提前到该点计算,可得: $$f[i][j]=\min\{f[k][j-1]+st[i]\cdot(sf[i]-sf[k])+S\cdot(sf[n]-sf[k])\}$$ 再考虑把 $j$滚动掉,就可以进行斜率优化了。

DAY 5

路径压缩

以前的笔记:路径压缩

也就是特殊的离散化,多半是用 LCM 来压路径。

需要注意的是,路径压缩只是把稀疏路径压缩成稠密路径,也就是说开空间还是要开到 MAXN * LCM 级别。

齐线法

齐线法有些搞忘了,甚至于该怎么写都有点懵。本质上来说,齐线法也是一个动态规划的过程,只是其状态由多个变量组成。

转移的时候,若上一行符合题意,则上一行的状态继承到当前行。为了保证取得的部分是合法的矩形,所以有些取 max()min() 的操作。

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 2080;
int n, m, a[MAXN][MAXN];
int l[MAXN][MAXN], r[MAXN][MAXN], h[MAXN][MAXN];
int ans1 = 0, ans2 = 0;
// ans1 - 正方形, ans2 - 长方形

inline int sq(int x) { return x * x; }

int main() {
    scanf("%d %d", &n, &m);
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++) {
            scanf("%d", &a[i][j]);
            l[i][j] = r[i][j] = j;
            h[i][j] = 1;
        }
    for (int i = 1; i <= n; i++)
        for (int j = 2; j <= m; j++)
            if (a[i][j] != a[i][j - 1])
                l[i][j] = l[i][j - 1];
    for (int i = 1; i <= n; i++)
        for (int j = m - 1; j; j--) 
            if (a[i][j] != a[i][j + 1])
                r[i][j] = r[i][j + 1];
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++) {
            if (i > 1 && a[i][j] != a[i - 1][j]) {
                l[i][j] = max(l[i][j], l[i - 1][j]);
                r[i][j] = min(r[i][j], r[i - 1][j]);
                h[i][j] = h[i - 1][j] + 1;
            }
            ans1 = max(ans1, sq(min(r[i][j] - l[i][j] + 1, h[i][j])));
            ans2 = max(ans2, (r[i][j] - l[i][j] + 1) * h[i][j]);
        }
    printf("%d\n%d", ans1, ans2);
    return 0;
}

DAY 6

只剩下最后一周了。

真的很累,很累。

所承受的一切,不知该向谁倾诉。

只是期盼着,暗夜中能再闪耀一粒星辰;

只是等待着,绝望中能再瞥见一缕亮光。

$\text{I tend to lose my sense of time and come the morning,}$

$\large\text{Stayed aside.}$

$\text{I know it's much too soon to tell you that I need you,}$

$\large\text{By my side.}$

$\text{But who are we to call each other selfish lovers?}$

$\Large\text{We all need someone to} \huge\text{ hold.}$

Hold $\footnotesize\texttt{Hold feat. Daniela Andrade}$