动态规划熟悉依旧-下

用户11956880

发布于 2025-12-18 18:18:34

610

接着上次的序章

A - 青蛙 1 社论

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

有N块石头，编号为1，2，…，N。对于每个i（1≤i≤N），石头i的高度为h_i。有一只青蛙最初在石头1上。它将重复以下动作若干次以到达石头N：如果青蛙目前位于石头i上，它可以跳到石头i+1或石头i+2。在这里，如果青蛙跳到石头j上，则会产生一个成本∣h_i − h_j∣，其中j是青蛙着陆的石头。找出青蛙在到达石头N之前可能产生的最小总成本。

约束条件输入中的所有值都是整数。

2≤N≤105
1≤hi≤104 Input 输入以下列格式从标准输入给出： N h1 h2 … hN Output 打印可能的最低总成本。

Sample Input 1 Copy 4 10 30 40 20 Sample Output 1 Copy 30 如果我们沿着路径1→2→4行进，产生的总成本将是∣10−30∣+∣30−20∣=30。

Sample Input 2 Copy 2 10 10 Sample Output 2 Copy 0 如果我们遵循路径1→2，产生的总成本将是∣10−10∣=0。

Sample Input 3 Copy 6 30 10 60 10 60 50 Sample Output 3 Copy 40 如果我们遵循路径 1 → 3 → 5 → 6，产生的总成本将是 ∣30−60∣+∣60−60∣+∣60−50∣=40。

思路：

青蛙可以一下跳1个石头或2个石头，然后一次消耗这个石头到那个石头的高度，现在问到达第N个石头最小消耗，我们就可以设dp数组的含义为到达每个石头最小消耗,我们可以得到这样的状态转移方程

dp[i]=min(dp[i-1]+abs(h[i]-h[i-1]),dp[i-2]+abs(h[i]-h[i-2]));

#include<bits/stdc++.h>
using namespace std;
#define int long long
int n;
int h[100020];
int dp[100020];
signed main(){
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>h[i];
	}
	dp[1]=0;
	dp[2]=abs(h[1]-h[2]);
	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 - 青蛙 2 社论

B - Frog 2

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

问题

有N块石头，编号为1，2，…，N。对于每个i（1≤i≤N），石头i的高度为h_i。有一只青蛙最初在石头1上。它将重复以下动作若干次以到达石头N：如果青蛙目前位于石头i上，它可以跳到以下石头之一：石头i+1，i+2，…，i+K。在这里，如果青蛙跳到石头j上，将产生一个成本∣h_i − h_j∣，其中j是青蛙着陆的石头。找出青蛙在到达石头N之前可能产生的最小总成本。

约束条件输入中的所有值都是整数。

2≤N≤105
1≤K≤100
1≤hi≤104 Input 输入以下列格式从标准输入给出： N K h1 h2 … hN Output 打印可能的最低总成本。

Sample Input 1 Copy 5 3 10 30 40 50 20 Sample Output 1 Copy 30 If we follow the path 1 → 2 → 5, the total cost incurred would be ∣10−30∣+∣30−20∣=30.

Sample Input 2 Copy 3 1 10 20 10 Sample Output 2 Copy 20 If we follow the path 1 → 2 → 3, the total cost incurred would be ∣10−20∣+∣20−10∣=20.

Sample Input 3 Copy 2 100 10 10 Sample Output 3 Copy 0 If we follow the path 1 → 2, the total cost incurred would be ∣10−10∣=0.

Sample Input 4 Copy 10 4 40 10 20 70 80 10 20 70 80 60 Sample Output 4 Copy 40 If we follow the path 1 → 4 → 8 → 10, the total cost incurred would be ∣40−70∣+∣70−70∣+∣70−60∣=40.

思路：

和上题不同的是这题可以从一个石头一直跳到第k个石头，然后重要的是

简化版本可以按顺序计算，确保每个状态只依赖已计算的状态；扩展版本需要初始化为无穷大来处理未计算的状态

#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,k;
int h[100020];
int dp[100020];
signed main(){
	cin>>n>>k;
	for(int i=1;i<=n;i++){
		cin>>h[i];
	}

	memset(dp,0x3f,sizeof(dp));
		dp[1]=0;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=k;j++){
			if(i+j>n) break; 
			dp[i+j]=min(dp[i+j],dp[i]+abs(h[i]-h[i+j]));
		}
	
	}
	cout<<dp[n];
	return 0; 
}

C - Vacation

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

Taro的暑假从明天开始，他已经决定现在就制定计划。

这次假期有N天。对于每个i（1≤i≤N），Taro将在第i天选择以下活动之一进行：

A：在海里游泳。获得a_i个幸福点。 B：在山中捉虫。获得b_i个幸福点。 C：在家做作业。获得c_i个幸福点。由于Taro很容易感到无聊，他不能连续两天做同样的活动。找出Taro可能获得的最大幸福总点数。

Constraints

All values in input are integers.
1≤N≤105
1≤ai,bi,ci≤104 Input Input is given from Standard Input in the following format: N a1 b1 c1 a2 b2 c2 : aN bN cN Output Print the maximum possible total points of happiness that Taro gains.

Sample Input 1 Copy 3 10 40 70 20 50 80 30 60 90 Sample Output 1 Copy 210 If Taro does activities in the order C, B, C, he will gain 70+50+90=210 points of happiness.

Sample Input 2 Copy 1 100 10 1 Sample Output 2 Copy 100

Sample Input 3 Copy 7 6 7 8 8 8 3 2 5 2 7 8 6 4 6 8 2 3 4 7 5 1 Sample Output 3 示例输出 3 复制 Copy 46 Taro should do activities in the order C, A, B, A, C, B, A.

思路：

跟上篇文章有道题差不多，就是三个选择，选a，b，c三种情况，我们用个二维dp数组来代表，分别是0 1 2

#include<bits/stdc++.h>
using namespace std;
int f[100020][3];
int main()
{
	int n;
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		int a,b,c;
		cin>>a>>b>>c;
		f[i][0]=max(f[i-1][1],f[i-1][2])+a;
		f[i][1]=max(f[i-1][0],f[i-1][2])+b;
		f[i][2]=max(f[i-1][0],f[i-1][1])+c;
	}
	cout<<max(f[n][0],max(f[n][1],f[n][2]))<<endl;
	return 0;
}

D - 背包 1 社论

D - 背包 1 --- D - Knapsack 1

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

有N个物品，编号为1，2，…，N。对于每个i（1≤i≤N），物品i的重量为wi，价值为vi。Taro决定选择一些物品放入背包中。背包的容量为W，这意味着所取物品的总重量不得超过W。找出Taro带回家的物品可能的最大价值总和。

Constraints

All values in input are integers.
1≤N≤100
1≤W≤105
1≤wi≤W
1≤vi≤109

Input

输入以以下格式从标准输入提供：

N W
w1 v1
w2 v2
:
wN vN

Output

打印Taro带回家的物品可能的最大价值总和。

Sample Input 1

Copy

Sample Output 1

Copy

应选取项目1和3。然后，权重的总和是3+5=8，价值的总和是30+60=90。

Sample Input 2

Copy

5 5
1 1000000000
1 1000000000
1 1000000000
1 1000000000
1 1000000000

Sample Output 2

Copy

5000000000

答案可能不适合32位整数类型。

Sample Input 3

Copy

Sample Output 3

Copy

应选取项目2、42、4和555。然后，权重的总和是5+6+3=14，价值的总和是6+6+5=17。

思路：

依旧是01背包的模板

#include<bits/stdc++.h>
using namespace std;
int n,w,a[100020],W[100020];
int dp[100020];
int main(){
	cin>>n>>w;
	for(int i=1;i<=n;i++){
		cin>>W[i]>>a[i];
	}
	for(int i=1;i<=n;i++){
		for(int j=w;j>=a[i];j--){
			dp[j]=max(dp[j],dp[j-W[i]]+a[i]);
		}
	}
	cout<<dp[w];
}

E - 背包 2 社论

E - Knapsack 2

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

1≤N≤100

1≤W≤10e9

1≤wi≤W

1≤vi≤10e3

Input 输入

Input is given from Standard Input in the following format: 输入从标准输入以以下格式提供：

N W
w1 v1
w2 v2
:
wN vN

Output 输出

Print the maximum possible sum of the values of items that Taro takes home. 打印 Taro 带回家的物品价值的最大可能总和。

Sample Input 1 样本输入 1Copy

Copy 复制

Sample Output 1 示例输出 1Copy

Copy 复制

Items 1 and 3 should be taken. Then, the sum of the weights is 3+5=8, and the sum of the values is 30+60=90. 物品 1 和 3 应该被带走。然后，权重之和为 3+5=8 ，值之和为 30+60=90 。

Sample Input 2 样本输入 2 复制

Copy 复制

1 1000000000
1000000000 10

Sample Output 2 示例输出 2 复制

Copy 复制

Sample Input 3 样本输入 3 复制

Copy 复制

Sample Output 3 示例输出 3 复制

Copy 复制

Items 2,4 and 5 should be taken. Then, the sum of the weights is 5+6+3=14, and the sum of the values is 6+6+5=17. 物品 2,4 和 5 应该被带走。然后，权重之和为 5+6+3=14 ，值之和为 6+6+5=17 。

思路：

数据变量，重量打到1e9了·我们的数组不能支持这么大的，所以我们要转换思路，

传统方法：定义数组dp[j]表示前i个物品在总重量不超过j时的最大价值。但由于W可能很大，数组会过于庞大，无法计算。

替代方法：定义数组f[j]表示达到价值j所需的最小总重量。因为总价值V最多为100,000，数组f的大小只需100,000左右，内存消耗合理。

最后我们再弄for循环从价值100000开始一直到0，谁对应的最小重量在给的V范围内就是最大价值了

#include<bits/stdc++.h>
using namespace std;
long long dp[100020];
int a[120];
int b[120];
int main()
{
	memset(dp,0x3f,sizeof(dp));
	f[0]=0;
	int v,n;
	cin>>n>>v;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i]>>b[i];
	}
	for(int i=1;i<=n;i++)
	{
		for(int j=100000;j>=b[i];j--)
		{
			dp[j]=min(dp[j],dp[j-b[i]]+a[i]);
		}
	}
	for(int i=100000;i>=0;i--)
	{
		if(dp[i]<=v)
		{
			cout<<i<<endl;
			return 0;
		}
	}
	return 0;
}

F - LCS 社论

F - LCS

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

问题陈述你会得到字符串 s 和 t .找到一个最长的字符串，它是 s 和 t 的子序列。笔记字符串的子序列 x 是通过从中 x 删除零个或多个字符并在不改变顺序的情况下连接其余字符而获得的字符串。约束 s 是由 t 小写英文字母组成的字符串。 1≤∣s∣,∣t∣≤3000

输入

输入从标准输入以以下格式提供：

s
t

打印一个最长的字符串，它是 s 和 t 的子序列。如果有多个这样的字符串，则将接受其中任何一个。

Sample Input 1 样本输入 1Copy

Copy 复制

axyb
abyxb

Sample Output 1 示例输出 1Copy

Copy 复制

axb

The answer is axb or ayb; either will be accepted. 答案是 axb 或 ayb ;任何一个都会被接受。

Sample Input 2 样本输入 2 复制

Copy 复制

aa
xayaz

Sample Output 2 示例输出 2 复制

Copy 复制

aa

Sample Input 3 样本输入 3 复制

Copy 复制

a
z

Sample Output 3 示例输出 3 复制

Copy 复制

The answer is (an empty string). 答案是（空字符串）。

Sample Input 4 样本输入 4Copy

Copy 复制

abracadabra
avadakedavra

Sample Output 4 示例输出 4Copy

Copy 复制

aaadara

思路

我们就按照之前的文章讲的那样，那个动态规划熟悉上，我们用n^2的做法，设dp[i][j]为s的前i个字符和t的前j个字符的最长公共子序列

然后我们再回溯一次记录出最长公共子序列是啥，这个具体看代码

#include<bits/stdc++.h>
using namespace std;
int main() {
    string s, t;
    cin >> s >> t;
    int n = s.size();
    int m = t.size();
    int dp[n + 1][m + 1];
    
    for (int i = 0; i <= n; i++) {
        for (int j = 0; j <= m; j++) {
            if (i == 0 || j == 0) {//s的前i个字符和t的前j个序列的最长公共子序列为0 
                dp[i][j] = 0;
            } else if (s[i - 1] == t[j - 1]) {
                dp[i][j] = dp[i - 1][j - 1] + 1;
            } else {
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
            }
        }
    }
    //开始回溯找到最长公共子序列 
    string lcs = "";
    int i = n, j = m;
    while (i > 0 && j > 0) {
        if (s[i - 1] == t[j - 1]) {
            lcs += s[i - 1];
            i--;
            j--;
        } else if (dp[i - 1][j] > dp[i][j - 1]) {
        	//这个情况说明s少一个更容易找到LCS 
            i--;
        } else {
        	//这个情况说明t少一个更容易找到LCS 
            j--;
        }
    }
    
    reverse(lcs.begin(), lcs.end());
    cout << lcs << endl;
    
    return 0;
}

H - 网格 1 社论

H - Grid 1

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

有一个带有水平行和 W 垂直列的 H 网格。让我们 (i,j) 表示从顶部开始的 i 第 - 行处的正方形和从左开始的 j 第 - 列处的正方形。对于每个 i 和 j （ 1≤i≤H ， 1≤j≤W ），Square (i,j) 由一个字符 ai,j 描述。如果是， . 则 ai,j Square (i,j) 是一个空正方形;如果是， # 则 ai,j Square (i,j) 是墙方。保证正方形 (1,1) 和 (H,W) 是空正方形。 Taro 将从广场 (1,1) 开始，通过反复向右或向下移动 (H,W) 到相邻的空方块到达。找出 Taro 从 Square (1,1) 到 (H,W) 的路径数。由于答案可能非常大，因此请找到计数模数 109+7 。

H 和 W 是整数。 2≤H,W≤1000 ai,j 是 . 或 # 。正方形 (1,1) 和 (H,W) 是空正方形。

Input 输入 输入从标准输入以以下格式提供：

H W
a1,1…a1,W
:
aH,1…aH,W

Output 输出 打印 Taro 从 Square (1,1) 到 (H,W) ，模的 109+7 路径数。

Sample Input 1 样本输入 1Copy

Copy 复制

3 4
...#
.#..
....

Sample Output 1 示例输出 1Copy

Copy 复制

There are three paths as follows: 有以下三种路径：

Sample Input 2 样本输入 2 复制

Copy 复制

5 2
..
#.
..
.#
..

Sample Output 2 示例输出 2 复制

Copy 复制

0

可能没有路径。

Sample Input 3 样本输入 3 复制

Copy 复制

5 5
..#..
.....
#...#
.....
..#..

Sample Output 3 示例输出 3 复制

Copy 复制

Sample Input 4 样本输入 4Copy

Copy 复制

20 20
....................
....................
....................
....................
....................
....................
....................
....................
....................
....................
....................
....................
....................
....................
....................
....................
....................
....................
....................
....................

Sample Output 4 示例输出 4Copy

Copy 复制

345263555
请务必打印计数模数 109+7 。

思路：

跟之前那个马走日那个题差不多

#include<bits/stdc++.h>
using namespace std;
const int mod=1e9+7;
int dp[1020][1020]; 
char a[1020][1020];
int main()
{
	int n,m;
	cin>>n>>m;
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=m;j++)
		{
			cin>>a[i][j];
		}
	}
	dp[0][1]=1;
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=m;j++)
		{
			if(a[i][j]=='#')continue;
			dp[i][j]=dp[i-1][j]+dp[i][j-1];
			dp[i][j]%=mod;
		}
	}
	cout<<dp[n][m]<<endl;
	return 0;
}

结束咯这次的动态规划

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2025-08-31，如有侵权请联系 cloudcommunity@tencent.com 删除

动态规划

数组

字符串

copy

本文分享自作者个人站点/博客前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体同步曝光计划，欢迎热爱写作的你一起参与！

登录后参与评论

0 条评论

热度