AtCoder Educational DP Contest

本文主要是介绍AtCoder Educational DP Contest，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

A - Frog 1

大意

有 $n$ 块石头，第 $i$ 块石头的高度为 $h_i$ 。从石头 $i$ 跳到石头 $j$ 的花费是 $|h_i-h_j|$ 。

一只青蛙在石头 $1$ 上，每次可以跳 $1$ 步或 $2$ 步，请问跳到石头 $n$ 的最小代价是多少？

$2 \le n \le 10^5, 1 \le h_i \le 10^4$

思路

设 $\operatorname{cost}(i,j)=|h_i-h_j|$ ， $dp_i$ 为青蛙跳到第 $i$ 号石头时的最小代价。

每一个点都可以由前两个点转移而来，因此状态转移方程为：

$dp_i=\min(dp_{i-1}+\operatorname{cost}(i-1,i), dp_{i-2}+\operatorname{cost}(i-2, i))$

边界可由定义得出： $dp_1=0,dp_2=\operatorname{cost}(1,2)$ 。

时间复杂度 $O(n)$

代码

#include <iostream>
#include <vector>
using namespace std;
#define int long long
signed main(){ios::sync_with_stdio(0);cin.tie(0), cout.tie(0);int n;cin >> n;vector<int> a(n + 1), dp(n + 1, 0);for(int i = 1; i <= n; i++) cin >> a[i];auto cost = [&](int i, int j) -> int{int ret = a[i] - a[j];if(ret < 0) ret = -ret;return ret;};dp[2] = cost(1, 2);for(int i = 3; i <= n; i++)dp[i] = min(dp[i - 1] + cost(i, i - 1), dp[i - 2] + cost(i, i - 2));cout << dp[n] << endl;return 0;
}

B - Frog 2

大意

有 $n$ 块石头，第 $i$ 块石头的高度为 $h_i$ 。从石头 $i$ 跳到石头 $j$ 的花费是 $|h_i-h_j|$ 。

一只青蛙在石头 $1$ 上，每次可以跳 $1$ ~ $k$ 步，请问跳到石头 $n$ 的最小代价是多少？

$2 \le n \le 10^5, 1 \le k \le 100, 1 \le h_i \le 10^4$

思路

和上一题一样，设 $\operatorname{cost}(i,j)=|h_i-h_j|$ ， $dp_i$ 为青蛙跳到第 $i$ 号石头时的最小代价。

每一个点都可以由前 $k$ 个点转移而来（除了 $i < k$ 的情况），因此状态转移方程为：

$dp_i=\min(dp_{i-1}+\operatorname{cost}(i-1,i), dp_{i-2}+\operatorname{cost}(i-2, i), \cdots, dp_{\max(1, i - k)} + \operatorname{cost}(\max(1, i - k), i))$

边界为 $dp_1=0$ 。

时间复杂度 $O(nk)$

代码

#include <iostream>
#include <vector>
using namespace std;
#define int long long
const int INF = 0x3f3f3f3f;
signed main(){ios::sync_with_stdio(0);cin.tie(0), cout.tie(0);int n, k;cin >> n >> k;vector<int> a(n + 1), dp(n + 1, INF);for(int i = 1; i <= n; i++) cin >> a[i];auto cost = [&](int i, int j){int ret = a[i] - a[j];return (ret > 0? ret: -ret);};dp[1] = 0;for(int i = 2; i <= n; i++){for(int j = max(1ll, i - k); j < i; j++) dp[i] = min(dp[i], dp[j] + cost(i, j));}cout << dp[n] << endl;
}

C - Vacation

大意

有 $n$ 天时间和 $3$ 种活动。每天只能进行一个活动，且相邻两天不能做相同的活动。

第 $i$ 天做三种活动分别可以获得 $a_i,b_i,c_i$ 点快乐值，求这 $n$ 天里最大可以获得多少点快乐值。

$1 \le n \le 10^5, 1 \le a_i,b_i,c_i \le 10^4$

思路

设 $dp_{i,j}$ 为考虑到第 $i$ 天，且第 $i$ 天进行活动 $j$ 的最大值。

由于相邻两天不能做相同的活动，所以 $dp_{i,j}$ 只能从另外两个状态中的最大值转移过来。、

因此，状态转移方程为：

$\begin{cases} dp_{i,1}=\max(dp_{i-1,2}, dp_{i-1,3}) + a_i \\ dp_{i,2}=\max(dp_{i-1,1}, dp_{i-1,3}) + b_i \\ dp_{i,3}=\max(dp_{i-1,1}, dp_{i-1,2}) + c_i \end{cases}$

边界为 $dp_{0,1}=dp_{0,2}=dp_{0,3}=0$ ，答案为 $\max(dp_{n,1}, dp_{n,2}, dp_{n,3})$ 。

时间复杂度 $O(n)$ 。

代码

#include <iostream>
#include <vector>
using namespace std;
#define int long longsigned main(){ios::sync_with_stdio(0);cin.tie(0), cout.tie(0);int n;cin >> n;vector<int> a(n + 1), b(n + 1), c(n + 1);vector<int> dp1(n + 1, 0), dp2(n + 1, 0), dp3(n + 1, 0);for(int i = 1; i <= n; i++) cin >> a[i] >> b[i] >> c[i];for(int i = 1; i <= n; i++){dp1[i] = max(dp2[i - 1], dp3[i - 1]) + a[i];dp2[i] = max(dp1[i - 1], dp3[i - 1]) + b[i];dp3[i] = max(dp1[i - 1], dp2[i - 1]) + c[i];}cout << max(dp1[n], max(dp2[n], dp3[n])) << endl;
}

D - Knapsack 1

大意

有 $n$ 件物品和一个承重量为 $m$ 千克的袋子。

第 $i$ 件物品的重量为 $w_i$ 千克，价值为 $v_i$ 元。

现在要挑选一些物品装入袋子里，求选择的物品的最大总价值。

$1 \le n\le 100, 1 \le m \le 10^5, 1 \le w_i \le m, 1 \le v_i \le 10^9$

思路

经典01背包问题，按照01背包的解法做即可。

注意需要long long。

时间复杂度 $O(nm)$

代码

#include <iostream>
#include <vector>
using namespace std;
#define int long longsigned main(){ios::sync_with_stdio(0);cin.tie(0), cout.tie(0);int n, m;cin >> n >> m;vector<int> w(n + 1), v(n + 1), dp(m + 1, 0);for(int i = 1; i <= n; i++) cin >> w[i] >> v[i];for(int i = 1; i <= n; i++)for(int j = m; j >= w[i]; j--)dp[j] = max(dp[j], dp[j - w[i]] + v[i]);cout << dp[m] << endl;return 0;
}

E - Knapsack 2

大意

有 $n$ 件物品和一个承重量为 $m$ 千克的袋子。

第 $i$ 件物品的重量为 $w_i$ 千克，价值为 $v_i$ 元。

现在要挑选一些物品装入袋子里，求选择的物品的最大总价值。

$1 \le n\le 100, 1 \le m \le 10^9, 1 \le w_i \le m, 1 \le v_i \le 10^3$

思路

$w_i$ 很大，直接套用01背包计算，时间和空间肯定一定炸。

由于 $v_i$ 很小，我们可以转换思路，设 $dp_{j}$ 为价值为 $j$ 的最小重量，这样就不会炸了。

最后从大到小遍历 $j$ ，找到符合 $dp_j \le m$ 的直接输出 $j$ 。

时间复杂度 $O(ns)$ ，其中 $s$ 为 $j$ 的取值范围， $s=\sum v_i$

代码

#include <iostream>
#include <vector>
using namespace std;
#define int long long
const int INF = 0x3f3f3f3f;signed main(){ios::sync_with_stdio(0);cin.tie(0), cout.tie(0);int n, m;cin >> n >> m;vector<int> w(n + 1), v(n + 1);int sum = 0;for(int i = 1; i <= n; i++){cin >> w[i] >> v[i];sum += v[i];}vector<int> dp(sum + 1, INF);dp[0] = 0;for(int i = 1; i <= n; i++)for(int j = sum; j >= v[i]; j--)dp[j] = min(dp[j], dp[j - v[i]] + w[i]);for(int j = sum; j >= 0; j--)if(dp[j] <= m){cout << j << endl;break;}return 0;
}

F - LCS

题意

给定两个字符串，输出它们的任意一个最长公共子序列。

思路

求LCS时将最优策略保存下来，用 $x_{i,j}$ 来表示状态 $(i,j)$ 是否和 $(i-1,j)$ 有关， $y_{i,j}$ 来表示状态 $(i,j)$ 是否和 $(i,j-1)$ 有关。

根据 $x$ 和 $y$ ，就可以递归输出方案。

代码

#include <iostream>
#include <vector>
using namespace std;
int main(){ios::sync_with_stdio(0);cin.tie(0), cout.tie(0);string x, y;cin >> x >> y;int n = x.size(), m = y.size();vector<vector<int>> dp(n + 1, vector<int>(m + 1));vector<vector<int>> f1(n + 1, vector<int>(m + 1));vector<vector<int>> f2(n + 1, vector<int>(m + 1));auto lcs = [&](string a, string b, int n, int m) -> void{for(int i = 1; i <= n; i++)for(int j = 1; j <= m; j++){if(a[i - 1] == b[j - 1]){dp[i][j] = dp[i - 1][j - 1] + 1;f1[i][j] = 1;f2[i][j] = 1;}else if(dp[i - 1][j] > dp[i][j - 1]){dp[i][j] = dp[i - 1][j];f1[i][j] = 1;}else{dp[i][j] = dp[i][j - 1];f2[i][j] = 1;}}};string ans = "";auto dfs = [&](auto self, string a, string b, int i, int j) -> void{if(i == 0 || j == 0) return;self(self, a, b, i - f1[i][j], j - f2[i][j]);if(a[i - 1] == b[j - 1]) ans.push_back(a[i - 1]);};lcs(x, y, n, m);dfs(dfs, x, y, n, m);cout << ans << endl;}

这篇关于AtCoder Educational DP Contest的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

AtCoder Educational DP Contest

A - Frog 1

大意

思路

代码

B - Frog 2

大意

思路

代码

C - Vacation

大意

思路

代码

D - Knapsack 1

大意

思路

代码

E - Knapsack 2

大意

思路

代码

F - LCS

题意

思路

代码

相关文章

hdu4826（三维DP）

hdu1011（背包树形DP）

hdu4865(概率DP)

usaco 1.1 Broken Necklace（DP）

uva 10154 DP 叠乌龟

uva 10118 dP

uva 10069 DP + 大数加法

uva 10029 HASH + DP

XTU 1233 n个硬币连续m个正面个数（dp）

dp算法练习题【8】