AtCoder DP Contest

lzyqwq · 2022-10-31 19:56:34 · 个人记录

前言

~~whkzbl，来水谷。~~

本篇博客是作者整理的 AtCoder DP Contest 的题解，其中还有几题待补。

题单简介：dp（即动态规划）是 OI 中一种非常重要的算法，这份 AtCoder DP Contest 题单里面的 26 题涵盖的 dp 类型较为齐全，难度由浅入深，对于初学者来说是练习的不二之选。

A.Frog 1

\texttt{Description}

有 n 个石头，第 i\,(i\le n) 个石头的高度为 h_i。有一只青蛙一开始站在石头 1 上，要跳到石头 n 去。青蛙站在石头 i 上时可以跳到石头 i+1 或石头 i+2。青蛙从石头 i 跳到石头 j 需要花费 |h_i-h_j| 的体力。求青蛙从石头 1 跳到石头 n 所需花费的最小体力值之和。

\texttt{Solution}

非常基础的动态规划了，设 f_i 为跳到石头 i 所花费的最小体力值之和，有：

f_i + |h_i-h_{i+1}|\longrightarrow f_{i+1}

f_i+|h_i-h_{i+2}|\longrightarrow f_{i+2}

这样转移考虑“当前状态转移给谁”，可以避免数组越界的问题，而且正确性可以保证。

初始化 f_1=0，f_i= \infty\,(2\le i\le n)。

时间复杂度和空间复杂度均为 \mathcal{O(n)}。

\texttt{Code}

#include <bits/stdc++.h>
using namespace std;
#define N 100005
int n, f[N], h[N];
int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i) {
        scanf("%d", h + i);
    }
    memset(f, 0x3f, sizeof(f));
    f[1] = 0;
    for (int i = 1; i <= n; ++i) {
        f[i + 1] = min(f[i + 1], f[i] + abs(h[i + 1] - h[i]));
        f[i + 2] = min(f[i + 2], f[i] + abs(h[i + 2] - h[i]));
    }
    printf("%d", f[n]);
}

B.Frog 2

\texttt{Description}

有 n 个石头，第 i\,(i\le n) 个石头的高度为 h_i。有一只青蛙一开始站在石头 1 上，要跳到石头 n 去。青蛙站在石头 i 上时可以跳到石头 i+1\sim i+k。青蛙从石头 i 跳到石头 j 需要花费 |h_i-h_j| 的体力。求青蛙从石头 1 跳到石头 n 所需花费的最小体力值之和。

\texttt{Solution}

类似于 A.Frog 1，非常基础的动态规划了，设 f_i 为跳到石头 i 所花费的最小体力值之和，有：

f_i + |h_i-h_j|\longrightarrow f_j\,(i+1\le j \le i+k)

这样转移考虑“当前状态转移给谁”，可以避免数组越界的问题，而且正确性可以保证。这里不需要考虑上界，因为超过 n 的状态是不会转移给任何状态的。

初始化 f_1=0，f_i= \infty\,(2\le i\le n)。

时间复杂度为 \mathcal{O(nk)}，空间复杂度为 \mathcal{O(n)}。

\texttt{Code}

#include <bits/stdc++.h>
using namespace std;
#define N 200005
int n, f[N], h[N], k;
int main() {
    scanf("%d%d", &n, &k);
    for (int i = 1; i <= n; ++i) {
        scanf("%d", h + i);
    }
    memset(f, 0x3f, sizeof(f));
    f[1] = 0;
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= k; ++j) {
            f[i + j] = min(f[i + j], f[i] + abs(h[i] - h[i + j]));
        }
    }
    printf("%d", f[n]);
}

C.Vacation

\texttt{Description}

太郎的暑假有 n 天，第 i 天他可以选择做以下三种事情：
1. 游泳，获得 a_i 点幸福值。
2. 捉虫，获得 b_i 点幸福值。
3. 写作业，获得 c_i 点幸福值。
但他不能连续两天进行同一种活动，请求大郎能获得出幸福值总和的最大值。

\texttt{Solution}

~~写作业居然有幸福值。~~

不难看出这题的状态为时间和事件，所以设 f_{i,j}\,(i\in\{0,1,2\}) 为前 j 天且第 j 天游泳、捉虫、写作业所得的最大幸福值总和。

设 a_{i,j}\,(i\in\{0,1,2\}) 为第 j 天游泳、捉虫、写作业所得的幸福值，有状态转移方程：

f_{i,j}=a_{i,j}+\max\limits_{k\ne i}f_{k,j-1}\,(i,k\in\{0,1,2\})

时间复杂度和空间复杂度均为 \mathcal{O}(n)。

\texttt{Code}

#include <bits/stdc++.h>
using namespace std;
int a[3][100005], f[3][100005], n;
int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i) {
        scanf("%d%d%d", &a[0][i], &a[1][i], &a[2][i]);
    }
    f[0][1] = a[0][1];
    f[1][1] = a[1][1];
    f[2][1] = a[2][1];
    for (int i = 2; i <= n; ++i) {
        f[0][i] = max(f[1][i - 1], f[2][i - 1]) + a[0][i];
    f[1][i] = max(f[0][i - 1], f[2][i - 1]) + a[1][i];
    f[2][i] = max(f[0][i - 1], f[1][i - 1]) + a[2][i];
    }
    printf("%d\n",max({f[0][n], f[1][n], f[2][n]}));
}

D.Knapsack 1

\texttt{Description}

有 n 种物品，每种物品只有一个，第 i 个物品有体积 w_i 和价值 v_i。你有一个容量为 m 体积的背包，问在不超过背包容积的情况下，所放物品的价值和最大是多少？

\texttt{Solution}

01 背包模板题了，设 f_{i,j} 为前 i 件物品选 j 件的最大价值和，考虑是否选取第 i 件物品。若选取，则相应地有前 i-1 件物品的体积剩下 j-w_i、第 i 件物品对当前状态下的价值和贡献 v_i；否则说明前 i-1 个物品已经取了 j 的体积、第 i 件物品对价值和无贡献。

若当前体积 j 足够容纳第 i 件物品，才能考虑是否选取，此时有状态转移方程：

f_{i,j}=\max\{f_{i-1,j},f_{i-1,j-w_i}+v_i\}

否则只能从前 i-1 件物品中选取，有状态转移方程：

f_{i,j}=f_{i-1,j}

时间复杂度和空间复杂度均为 \mathcal{O}(nm)。

不过可以用滚动数组将空间优化成 \mathcal{O}(m)。

\texttt{Code}

不开 long long 见祖宗！

naive 版本：

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 105, M = 1e5 + 1;
int n, m, w[N], v[N], f[N][M];
signed main() {
    scanf("%lld%lld", &n, &m);
    for (int i = 1; i <= n; ++i) {
        scanf("%lld%lld", w + i, v + i);
    }
    for (int i = 1; i <= n; ++i) {
        for (int j = 0; j <= m; ++j) {
            if (j < w[i]) {
                f[i][j] = f[i - 1][j];
            } else {
                f[i][j] = max(f[i - 1][j], f[i - 1][j - w[i]] + v[i]);
            }
        }
    }
    printf("%lld", f[n][m]);
}

滚动数组优化版本：

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 105, M = 1e5 + 1;
int n, m, w[N], v[N], f[M];
signed main() {
    scanf("%lld%lld", &n, &m);
    for (int i = 1; i <= n; ++i) {
        scanf("%lld%lld", w + i, v + i);
    }
    for (int i = 1; i <= n; ++i) {
        for (int j = m; j >= w[i]; --j) {//倒序
            f[j] = max(f[j], f[j - w[i]] + v[i]);
            //由于倒着循环以及 = 是从右到左执行，所以执行 max 语句时 f[j] 和 f[j - w[i]] 仍未被更新，是由 i - 1 时的状态转移的
            //对于 j < w[i] 的部分，应该由 f[i - 1][j] 来转移，这里没去动它，它仍旧是 i - 1 时的状态
        }
    }
    printf("%lld", f[m]);
}

E.Knapsack 2

\texttt{Description}

有 n 种物品，每种物品只有一个，第 i 个物品有体积 w_i 和价值 v_i。你有一个容量为 m 体积的背包，问在不超过背包容积的情况下，所放物品的价值和最大是多少？

\texttt{Solution}

题面与 D.Knapsack 1 类似，但是一看值域，\mathcal{O(nm)} 的时间复杂度显然过不去，我们不能使用上一题的方法。

然而价值的值域很小，于是我们反过来想，对于取成同一种价值，显然体积越小越优，所以可以设 f_{i,j} 为前 i 件物品，取成 j 的价值所需最小体积，类似地，考虑选取或不选取（这里不再赘述，有疑惑可类比 D.Knapsack 1），有状态转移方程：

f_{i,j}=\min\{f_{i-1,j},f_{i-1,j-v_i}+w_i\}

有初始化 f_{0,0}=0，f_{i,j}=\infty\,(i>0\,\lor\,j>0)。很好理解，一件物品都不去价值为 0，体积也为 0，其余状态需要转移得到，赋成正无穷可以在 \min 中自动舍去初值的贡献，从而达到正确的转移。

最后从大到小枚举价值，如果取成该价值的最小体积不超过容积，则该价值为答案（因为最小的体积不超过，那么去成最小的体积就是一种合法的方案，否则最小的体积都超过容积了，其它方案肯定都超过容积了，故不是一个合法的解），因为是从大到小枚举，所以可以保证最优。

同理用滚动数组优化，做到时间复杂度为 \mathcal{O(n\times \sum\limits_{i=1}^nv_i)}，空间复杂度为 \mathcal{O(\sum\limits_{i=1}^nv_i)}，可以通过本题。

\texttt{Code}

不开 long long 见祖宗！~~貌似可以不开。~~

这里只给出滚动数组优化版本：

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 105, M = 1e5 + 5;
int f[M], v[N], w[N], n, m, s;
signed main() {
    scanf("%lld%lld", &n, &m);
    for (int i = 1; i <= n; ++i) {
        scanf("%lld%lld", w + i, v + i);
        s += v[i];
    }
    memset(f, 0x3f, sizeof(f));
    f[0] = 0;
    for (int i = 1; i <= n; ++i) {
        for (int j = s; j >= v[i]; --j) {
            f[j] = min(f[j], f[j - v[i]] + w[i]);
        }
    }
    for (int j = s; ~j; --j) {
        if (f[j] <= m) {
            return !printf("%lld",j);
        }
    }
}

F.LCS

\texttt{Description}

给出字符串 s,t，求 s,t 的最长公共子序列，并输出任意一个解。

\texttt{Solution}

求最长公共子序列是比较模板的了，设 f_{i,j} 为 s 的前 i 个字符，t 的前 j 个字符中最长公共子序列的长度，有状态转移方程：

f_{i,j}=\begin{cases}f_{i-1,j-1}+1,s_i=t_j\\\max\{f_{i-1,j},f_{i,j-1}\},s_i\ne t_j\end{cases}

解释一下：

若 s_i=t_j，那么显然将 s_i 和 t_j 对应是最优的，因为若 s_i 或 t_j 与 j 或 i 之前的字符对应，那么让它们与第 t_j 或 s_i 对应，不会影响答案最优。
若 s_i\ne t_j，那么 s_i 不能和 t_j 对应，这两个字符可能和 j 之前或 i 之前的字符对应。

这样就可以推出上面那个方程，f_{|s|,|t|} 即为最长公共子序列的长度。

关键在于构造方案。考虑倒着枚举 i,j，看一下 f_{i,j} 是从哪个状态转移过来的，若 s_i=t_j，根据上面的方程，说明 s_i 与 t_j 对应，即最长公共子序列中有 s_i 和 t_j，将其计入答案即可。由于是倒着记录，最后也要倒序输出。

时间复杂度和空间复杂度均为 \mathcal{O(|s|\times |t|)}。

\texttt{Code}

#include<bits/stdc++.h>
using namespace std;
#define N 3005
char s[N], t[N], ans[N];
int f[N][N], n, m, k;
int main() {
    scanf("%s%s", s+1, t+1);
    n = strlen(s + 1);
    m = strlen(t + 1);
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) {
            f[i][j] = s[i] == t[j] ? f[i - 1][j - 1] + 1 : max(f[i - 1][j], f[i][j - 1]);
        }
    }
    while (n && m) {
        if (s[n] == t[m]) {
            ans[++k] = s[n--];
            --m;
        } else if (f[n][m] == f[n - 1][m]) {
            --n;
        } else {
            --m;
        }
    }
    for (int i = k; i; --i) {
        putchar(ans[i]);
    }
}