当前位置：首页 > news >正文

CSP2025考前恶补Ⅰ：DP

news 2026/3/26 20:06:38

题单：AtCoder 的 Educational DP Contest：https://atcoder.jp/contests/dp

A - Frog 1

有 \(N\) 个台阶。每个台阶编号为 \(1, 2, \ldots, N\)。对于每个 \(i\)（\(1 \leq i \leq N\)），第 \(i\) 个台阶的高度为 \(h_i\)。

一只青蛙最初在第 \(1\) 个台阶上。青蛙可以重复以下操作，试图到达第 \(N\) 个台阶：

当青蛙在第 \(i\) 个台阶时，可以跳到第 \(i+1\) 或第 \(i+2\) 个台阶。跳到目标台阶 \(j\) 时，需要支付的代价为 \(|h_i - h_j|\)。

请你求出青蛙到达第 \(N\) 个台阶所需支付的总代价的最小值。

水题。设 \(dp(i)\) 表示青蛙跳到 \(i\) 时的最小花费，决策是从前一个还是前两个台阶跳过来。

\[dp(i)=\min \left\{dp(i-1)+|h_i-h_{j-1}|,dp(i-2)+|h_i-h_{i-2}|\right\} \]

https://atcoder.jp/contests/dp/submissions/70493499

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
constexpr int N=1e5+7;
int n,h[N];
ll dp[N];
int main()
{
//	freopen("neuvillette.in","r",stdin);
//	freopen("neuvillette.out","w",stdout);cin>>n;for(int i=1;i<=n;i++) cin>>h[i];dp[1]=0; dp[2]=dp[1]+abs(h[2]-h[1]);for(int i=3;i<=n;i++){dp[i]=min(dp[i-1]+abs(h[i]-h[i-1]),dp[i-2]+abs(h[i]-h[i-2]));}cout<<dp[n];return 0;
}

B - Frog 2

有 \(N\) 个台阶。每个台阶编号为 \(1, 2, \ldots, N\)。对于每个 \(i\)（\(1 \leq i \leq N\)），第 \(i\) 个台阶的高度为 \(h_i\)。

一只青蛙最初站在第 \(1\) 个台阶上。青蛙可以多次进行如下操作，试图到达第 \(N\) 个台阶：

当青蛙在第 \(i\) 个台阶时，可以跳到第 \(i+1, i+2, \ldots, i+K\) 中的任意一个台阶。假设跳到第 \(j\) 个台阶，则需要支付的代价为 \(|h_i - h_j|\)。

请你求出青蛙到达第 \(N\) 个台阶所需支付的总代价的最小值。

这次只要把从 \(i-1/i-2\) 个台阶转移过来改成从 \(i-j_{(j \in [1,k])}\) 转移过来就好了。

https://atcoder.jp/contests/dp/submissions/70493592

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
constexpr int N=1e5+7;
int n,k;
ll h[N],dp[N];
int main()
{
//	freopen("neuvillette.in","r",stdin);
//	freopen("neuvillette.out","w",stdout);cin>>n>>k;for(int i=1;i<=n;i++) cin>>h[i];dp[1]=0;for(int i=2;i<=n;i++){ll res=1e18;for(int j=1;j<=k;j++)if(i-j>0) res=min(res,dp[i-j]+abs(h[i]-h[i-j]));dp[i]=res;}
//	for(int i=1;i<=n;i++) cerr<<dp[i]<<" \n"[i==n];cout<<dp[n];return 0;
}

C - Vacation

暑假有 \(N\) 天。对于每一天 \(i\)（\(1 \leq i \leq N\)），太郎君可以选择以下活动之一：

A：在海里游泳，获得幸福度 \(a _ i\)。

B：在山上抓虫，获得幸福度 \(b _ i\)。

C：在家做作业，获得幸福度 \(c _ i\)。

由于太郎君容易厌倦，他不能连续两天及以上做同样的活动。

请计算太郎君可以获得的最大总幸福度。

如果不考虑活动的选择，直接考虑到第 \(i\) 天的最大价值就会发现有后效性，因为当前选择的活动会影响后面的活动。所以直接设 \(dp(i,\{0,1,2\})\) 表示第 \(i\) 天选择活动 \(A/B/C\) 的最大价值。

https://atcoder.jp/contests/dp/submissions/70495398

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
constexpr int N=1e5+7;
int n;
ll a[N],b[N],c[N];
ll dp[N][3];
int main()
{
//	freopen("neuvillette.in","r",stdin);
//	freopen("neuvillette.out","w",stdout);cin>>n;for(int i=1;i<=n;i++) cin>>a[i]>>b[i]>>c[i];for(int i=1;i<=n;i++){dp[i][0]=max(dp[i-1][1],dp[i-1][2])+a[i]; dp[i][1]=max(dp[i-1][0],dp[i-1][2])+b[i]; dp[i][2]=max(dp[i-1][0],dp[i-1][1])+c[i]; }cout<<max({dp[n][0],dp[n][1],dp[n][2]});return 0;
}
/*
dp[i][0-2]表示第i天选择活动0-2的最大价值 
*/

D - Knapsack 1

有 \(N\) 个物品。每个物品编号为 \(1, 2, \ldots, N\)。对于每个 \(i\)（\(1 \leq i \leq N\)），物品 \(i\) 的重量为 \(w_i\)，价值为 \(v_i\)。

太郎君打算从这 \(N\) 个物品中选择一些，放入背包带回家。背包的容量为 \(W\)，所选物品的总重量不能超过 \(W\)。

请你求出太郎君能带回家的物品的最大总价值。

所有输入均为整数。

\(1 \leq N \leq 100\)

\(1 \leq W \leq 10^5\)

\(1 \leq w_i \leq W\)

\(1 \leq v_i \leq 10^9\)

0-1 背包超级模板题。设 \(dp(i,j)\) 表示考虑 \(1 \sim i\) 个物品，背包装了 \(j\) 重量的物品的最大价值。每一次考虑选不选这个物品即可。

https://atcoder.jp/contests/dp/tasks/dp_d

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
constexpr int N=1e5+7;
int n;
ll a[N],b[N],c[N];
ll dp[N][3];
int main()
{
//	freopen("neuvillette.in","r",stdin);
//	freopen("neuvillette.out","w",stdout);cin>>n;for(int i=1;i<=n;i++) cin>>a[i]>>b[i]>>c[i];for(int i=1;i<=n;i++){dp[i][0]=max(dp[i-1][1],dp[i-1][2])+a[i]; dp[i][1]=max(dp[i-1][0],dp[i-1][2])+b[i]; dp[i][2]=max(dp[i-1][0],dp[i-1][1])+c[i]; }cout<<max({dp[n][0],dp[n][1],dp[n][2]});return 0;
}
/*
dp[i][0-2]表示第i天选择活动0-2的最大价值 
*/

E - Knapsack 2

\(N\) 个物品被编号为 \(1, 2, \ldots, N\)。对于 \(1 \leq i \leq N\)，物品 \(i\) 的重量是 \(w _ i\)，价值是 \(v _ i\)。

太郎君决定从 \(N\) 个物品中选择一些放入背包中带回家。背包的容量为 \(W\)，带回的物品的总重量不能超过 \(W\)。

请计算太郎君能带回的物品的最大总价值。

\(1 \leq N \leq 100\)

\(1 \leq W \leq 10 ^ 9\)

\(1 \leq w _ i \leq W\)

\(1 \leq v _ i \leq 10 ^ 3\)