题解【动态规划1】"/>
洛谷题单题解【动态规划1】
蒟蒻记忆力有限,写个题解存下做题思路。欢迎指正错误!
目录
- 普及-
- P1216数字三角形
- P1048 采药# [NOIP2005 普及组] 采药
- 题目描述
- 解题思路
- AC代码
- P1115 最大子段和
- 题目描述
- 解题思路
- AC代码
- P1802 5倍经验日
- 题目描述
- 解题思路
- AC代码
- P1002 过河卒
- 题目描述
- 解题思路
- AC代码
- P1049 装箱问题
- 题目描述
- 解题思路
- AC代码
- P1616 疯狂的采药
- 题目描述
- 解题思路
- AC代码
- P1164 小A点菜
- 题目描述
- 解题思路
- AC代码
- 普及/提高-
- P1434 滑雪
- 题目描述
- 解题思路
- AC代码
- 普及+/提高
普及-
P1216数字三角形
P1048 采药# [NOIP2005 普及组] 采药
题目描述
辰辰是个天资聪颖的孩子,他的梦想是成为世界上最伟大的医师。为此,他想拜附近最有威望的医师为师。医师为了判断他的资质,给他出了一个难题。医师把他带到一个到处都是草药的山洞里对他说:“孩子,这个山洞里有一些不同的草药,采每一株都需要一些时间,每一株也有它自身的价值。我会给你一段时间,在这段时间里,你可以采到一些草药。如果你是一个聪明的孩子,你应该可以让采到的草药的总价值最大。”
如果你是辰辰,你能完成这个任务吗?
输入格式
第一行有 2 2 2 个整数 T T T( 1 ≤ T ≤ 1000 1 \le T \le 1000 1≤T≤1000)和 M M M( 1 ≤ M ≤ 100 1 \le M \le 100 1≤M≤100),用一个空格隔开, T T T 代表总共能够用来采药的时间, M M M 代表山洞里的草药的数目。
接下来的 M M M 行每行包括两个在 1 1 1 到 100 100 100 之间(包括 1 1 1 和 100 100 100)的整数,分别表示采摘某株草药的时间和这株草药的价值。
输出格式
输出在规定的时间内可以采到的草药的最大总价值。
样例 #1
样例输入 #1
70 3
71 100
69 1
1 2
样例输出 #1
3
提示
【数据范围】
- 对于 30 % 30\% 30% 的数据, M ≤ 10 M \le 10 M≤10;
- 对于全部的数据, M ≤ 100 M \le 100 M≤100。
【题目来源】
NOIP 2005 普及组第三题
解题思路
根据题目描述,得知有总容积,每株药草都不同,即每件物品只有一个,且都有其价值与容积。因此可以得出这是一个01背包板子题。
好水的题解啊
AC代码
#include<iostream>
using namespace std;
const int N=1005;
int v[N],w[N];
int dp[N][N];int main()
{int t,m;cin>>t>>m;for(int i=1;i<=m;i++){cin>>v[i]>>w[i];}for(int i=1;i<=m;i++){for(int j=1;j<=t;j++){if(j>=v[i]){dp[i][j]=max(dp[i-1][j],dp[i-1][j-v[i]]+w[i]);//01背包公式 }else dp[i][j]=dp[i-1][j];}}cout<<dp[m][t];
}
P1115 最大子段和
题目描述
给出一个长度为 n n n 的序列 a a a,选出其中连续且非空的一段使得这段和最大。
输入格式
第一行是一个整数,表示序列的长度 n n n。
第二行有 n n n 个整数,第 i i i 个整数表示序列的第 i i i 个数字 a i a_i ai。
输出格式
输出一行一个整数表示答案。
样例 #1
样例输入 #1
7
2 -4 3 -1 2 -4 3
样例输出 #1
4
提示
样例 1 解释
选取 [ 3 , 5 ] [3, 5] [3,5] 子段 { 3 , − 1 , 2 } \{3, -1, 2\} {3,−1,2},其和为 4 4 4。
数据规模与约定
- 对于 40 % 40\% 40% 的数据,保证 n ≤ 2 × 1 0 3 n \leq 2 \times 10^3 n≤2×103。
- 对于 100 % 100\% 100% 的数据,保证 1 ≤ n ≤ 2 × 1 0 5 1 \leq n \leq 2 \times 10^5 1≤n≤2×105, − 1 0 4 ≤ a i ≤ 1 0 4 -10^4 \leq a_i \leq 10^4 −104≤ai≤104。
解题思路
对于这道题,我们可以枚举找出以arr[i]结尾的最大的序列和,用dp[i]来存储。
那么,如何找出dp[i]呢?
在输入的时候,进行一个判断:
如果加上i对应的值,序列和变大或不变(不影响结果),选择i-1时的序列加上i对应的值;
如果序列和变小,就只选择i-1时的序列。
注:dp[i]最小是它本身,也就是arr[i]。
我们用max函数可以实现这个判断操作,得到状态转移方程:
d p [ i ] = m a x ( a r r [ i ] , d p [ i − 1 ] + a r r [ i ] ) dp[i] = max(arr[i],dp[i-1]+arr[i]) dp[i]=max(arr[i],dp[i−1]+arr[i])
最后再遍历dp数组,找出dp数组的最大值输出即可。
AC代码
#include<bits/stdc++.h>
using namespace std;const int N = 2e5+5;int arr[N],dp[N],n;
int ans = -9999999;int main()
{memset(dp,0,sizeof(dp));cin>>n;for(int i=1;i<=n;i++){cin>>arr[i];dp[i] = max(arr[i],1);dp[i] = max(dp[i],dp[i-1]+arr[i]);ans = max(dp[i],ans);}cout<<ans;
}
P1802 5倍经验日
题目背景
现在乐斗有活动了!每打一个人可以获得 5 倍经验!absi2011 却无奈的看着那一些比他等级高的好友,想着能否把他们干掉。干掉能拿不少经验的。
题目描述
现在 absi2011 拿出了 x x x 个迷你装药物(嗑药打人可耻…),准备开始与那些人打了。
由于迷你装药物每个只能用一次,所以 absi2011 要谨慎的使用这些药。悲剧的是,用药量没达到最少打败该人所需的属性药药量,则打这个人必输。例如他用 2 2 2 个药去打别人,别人却表明 3 3 3 个药才能打过,那么相当于你输了并且这两个属性药浪费了。
现在有 n n n 个好友,给定失败时可获得的经验、胜利时可获得的经验,打败他至少需要的药量。
要求求出最大经验 s s s,输出 5 s 5s 5s。
输入格式
第一行两个数, n n n 和 x x x。
后面 n n n 行每行三个数,分别表示失败时获得的经验 l o s e i \mathit{lose}_i losei,胜利时获得的经验 w i n i \mathit{win}_i wini 和打过要至少使用的药数量 u s e i \mathit{use}_i usei。
输出格式
一个整数,最多获得的经验的五倍。
样例 #1
样例输入 #1
6 8
21 52 1
21 70 5
21 48 2
14 38 3
14 36 1
14 36 2
样例输出 #1
1060
提示
【Hint】
五倍经验活动的时候,absi2011 总是吃体力药水而不是这种属性药。
【数据范围】
- 对于 10 % 10\% 10% 的数据,保证 x = 0 x=0 x=0。
- 对于 30 % 30\% 30% 的数据,保证 0 ≤ n ≤ 10 0\le n\le 10 0≤n≤10, 0 ≤ x ≤ 20 0\le x\le 20 0≤x≤20。
- 对于 60 % 60\% 60% 的数据,保证 0 ≤ n , x ≤ 100 0\le n,x\le 100 0≤n,x≤100, 10 < l o s e i , w i n i ≤ 100 10<lose_i,win_i\le 100 10<losei,wini≤100, 0 ≤ u s e i ≤ 5 0\le use_i\le 5 0≤usei≤5。
- 对于 100 % 100\% 100% 的数据,保证 0 ≤ n , x ≤ 1 0 3 0\le n,x\le 10^3 0≤n,x≤103, 0 < l o s e i ≤ w i n i ≤ 1 0 6 0<lose_i\le win_i\le 10^6 0<losei≤wini≤106, 0 ≤ u s e i ≤ 1 0 3 0\le use_i\le 10^3 0≤usei≤103。
【题目来源】
fight.pet.qq
absi2011 授权题目
解题思路
这道题看上去题目略有些繁琐,但是屏蔽掉一些无关紧要的词汇,就可以发现,这其实是一道01背包的变式题。
为什么呢?
这道题中,每个物品都有lose 和 win两个价值,也就是说,如果在普通01背包的dp操作时多加入一个判断——选择输的价值或赢的价值,就可以转化为01背包问题了。
如何转换?
1.所拥有的药水比对手多,可以选择赢或输他。
那么这个物品对应的dp即为max(选择赢的价值,选择输的价值)。
如果搞他,对应要减去用掉的药水数,加上赢得的价值。
如果不搞,就不用减去药水数(因为没用),加上输得的价值。
由此得到状态转移方程:
d p [ i ] [ j ] = m a x ( d p [ i − 1 ] [ j − b e a t [ i ] ] + w i n [ i ] , d p [ i − 1 ] [ j ] + l o s e [ i ] ) dp[i][j] = max(dp[i-1][j-beat[i]]+win[i],dp[i-1][j]+lose[i]) dp[i][j]=max(dp[i−1][j−beat[i]]+win[i],dp[i−1][j]+lose[i])
2.所拥有的药水比对手少,只能选择输给他。
首先声明,如果你智商健全的话,大概是不会白白用掉道具打一盘必输局的!
那么,对应的dp就只用加上输得的价值。
由此得到状态转移方程:
d p [ i ] [ j ] = d p [ i − 1 ] [ j ] + l o s e [ i ] dp[i][j] = dp[i-1][j]+lose[i] dp[i][j]=dp[i−1][j]+lose[i]
最后输出即可。
别忘了乘5!博主最喜欢犯低级错误了
AC代码
#include<bits/stdc++.h>
using namespace std;
const int N = 10005;int n,m;
long long lose[N],win[N],beat[N];
//分别记录输的经验值,赢的经验值,需要的药水个数(即物品容积)long long dp[N][N];int main()
{cin>>n>>m;for(int i=1;i<=n;i++){cin>>lose[i]>>win[i]>>beat[i];} for(int i=1;i<=n;i++){for(int j=0;j<=m;j++){dp[i][j] = dp[i-1][j]+lose[i];if(j >= beat[i]) dp[i][j] = max(dp[i-1][j-beat[i]]+win[i],dp[i-1][j]+lose[i]);} }cout<<5*dp[n][m];
}
P1002 过河卒
题目描述
棋盘上 A A A 点有一个过河卒,需要走到目标 B B B 点。卒行走的规则:可以向下、或者向右。同时在棋盘上 C C C 点有一个对方的马,该马所在的点和所有跳跃一步可达的点称为对方马的控制点。因此称之为“马拦过河卒”。
棋盘用坐标表示, A A A 点 ( 0 , 0 ) (0, 0) (0,0)、 B B B 点 ( n , m ) (n, m) (n,m),同样马的位置坐标是需要给出的。
现在要求你计算出卒从 A A A 点能够到达 B B B 点的路径的条数,假设马的位置是固定不动的,并不是卒走一步马走一步。
输入格式
一行四个正整数,分别表示 B B B 点坐标和马的坐标。
输出格式
一个整数,表示所有的路径条数。
样例 #1
样例输入 #1
6 6 3 3
样例输出 #1
6
提示
对于 100 % 100 \% 100% 的数据, 1 ≤ n , m ≤ 20 1 \le n, m \le 20 1≤n,m≤20, 0 ≤ 0 \le 0≤ 马的坐标 ≤ 20 \le 20 ≤20。
【题目来源】
NOIP 2002 普及组第四题
解题思路
啊好眼熟,让我想起一位名叫bfs的故人
这道题也算一个dp的板子题吧,不过多加了一步查找与判断。
大概的思路:设置一个dp数组一个bool数组,bool数组用于判断这个地方是不是“马”的地盘,如果是,直接跳过。如果不是,就根据题目要求做dp。
AC代码
#include<bits/stdc++.h>
using namespace std;int nex[] = {0, -2, -1, 1, 2, 2, 1, -1, -2};
int ney[] = {0, 1, 2, 2, 1, -1, -2, -2, -1};
//遍历八个以x2,y2为中心的"马" long long dp[40][40];//存储路径
bool horse[40][40];//是不是马的地盘 int main()
{int x1,y1,x2,y2;cin>>x1>>y1>>x2>>y2;x1+=2;y1+=2;x2+=2;y2+=2;//防止数组越界,这里+=2 dp[2][1] = 1;//inithorse[x2][y2] = 1;//马老大的位置不能走 for(int i=1;i<=8;i++){horse[x2+nex[i]][y2+ney[i]] = 1;//遍历8个马小弟的位置,标记为不能走 }for(int i=2;i<=x1;i++){for(int j=2;j<=y1;j++){if(horse[i][j]) continue;//如果被马占领,跳过 else dp[i][j] = dp[i-1][j]+dp[i][j-1];//可以走,做dp//i-1对应往右走,j-1对应往下走。 }}cout<<dp[x1][y1];return 0;
}
P1049 装箱问题
题目描述
有一个箱子容量为 V V V,同时有 n n n 个物品,每个物品有一个体积。
现在从 n n n 个物品中,任取若干个装入箱内(也可以不取),使箱子的剩余空间最小。输出这个最小值。
输入格式
第一行共一个整数 V V V,表示箱子容量。
第二行共一个整数 n n n,表示物品总数。
接下来 n n n 行,每行有一个正整数,表示第 i i i 个物品的体积。
输出格式
- 共一行一个整数,表示箱子最小剩余空间。
样例 #1
样例输入 #1
24
6
8
3
12
7
9
7
样例输出 #1
0
提示
对于 100 % 100\% 100% 数据,满足 0 < n ≤ 30 0<n \le 30 0<n≤30, 1 ≤ V ≤ 20000 1 \le V \le 20000 1≤V≤20000。
【题目来源】
NOIP 2001 普及组第四题
解题思路
啊我大吃一惊……这不就完全背包板子题!
只需要套用完全背包模板,最后用总体积v减一下最后一个dp即可。
AC代码
#include<iostream>
const int N=20005;using namespace std;int v,n;
int arr[35];
int dp[35][N];int main()
{cin>>v>>n;for(int i= 1;i <= n; i++){cin>>arr[i];}for(int i = 1;i <= n; i++){for(int j = 1; j <= v; j++){if(j>=arr[i]){dp[i][j]=max(dp[i-1][j],dp[i-1][j-arr[i]]+arr[i]);}else dp[i][j]=dp[i-1][j];}} cout<<v-dp[n][v];
}
P1616 疯狂的采药
题目背景
此题为纪念 LiYuxiang 而生。
题目描述
LiYuxiang 是个天资聪颖的孩子,他的梦想是成为世界上最伟大的医师。为此,他想拜附近最有威望的医师为师。医师为了判断他的资质,给他出了一个难题。医师把他带到一个到处都是草药的山洞里对他说:“孩子,这个山洞里有一些不同种类的草药,采每一种都需要一些时间,每一种也有它自身的价值。我会给你一段时间,在这段时间里,你可以采到一些草药。如果你是一个聪明的孩子,你应该可以让采到的草药的总价值最大。”
如果你是 LiYuxiang,你能完成这个任务吗?
此题和原题的不同点:
1 1 1. 每种草药可以无限制地疯狂采摘。
2 2 2. 药的种类眼花缭乱,采药时间好长好长啊!师傅等得菊花都谢了!
输入格式
输入第一行有两个整数,分别代表总共能够用来采药的时间 t t t 和代表山洞里的草药的数目 m m m。
第 2 2 2 到第 ( m + 1 ) (m + 1) (m+1) 行,每行两个整数,第 ( i + 1 ) (i + 1) (i+1) 行的整数 a i , b i a_i, b_i ai,bi 分别表示采摘第 i i i 种草药的时间和该草药的价值。
输出格式
输出一行,这一行只包含一个整数,表示在规定的时间内,可以采到的草药的最大总价值。
样例 #1
样例输入 #1
70 3
71 100
69 1
1 2
样例输出 #1
140
提示
数据规模与约定
- 对于 30 % 30\% 30% 的数据,保证 m ≤ 1 0 3 m \le 10^3 m≤103 。
- 对于 100 % 100\% 100% 的数据,保证 1 ≤ m ≤ 1 0 4 1 \leq m \le 10^4 1≤m≤104, 1 ≤ t ≤ 1 0 7 1 \leq t \leq 10^7 1≤t≤107,且 1 ≤ m × t ≤ 1 0 7 1 \leq m \times t \leq 10^7 1≤m×t≤107, 1 ≤ a i , b i ≤ 1 0 4 1 \leq a_i, b_i \leq 10^4 1≤ai,bi≤104。
解题思路
这道题根据数据大小,主要考察的是完全背包的空间优化,之前也写过所以直接放代码了。
数组别忘记开long long,不然会WA,别问我怎么知道,翻完了所有的题解都没发现哪里错了,最后被这个蒟蒻错误甜蜜暴击。
AC代码
#include<iostream>
const long long N=1e7+5;
using namespace std;
long long dp[N];
long long v[N],w[N];int main()
{int n,V;cin>>V>>n;for(int i=1;i<=n;i++){cin>>v[i]>>w[i];}for(int i=1;i<=n;i++){for(int j=v[i];j<=V;j++){dp[j] = max(dp[j],dp[j-v[i]]+w[i]);}}cout<<dp[V];}
P1164 小A点菜
题目背景
uim 神犇拿到了 uoi 的 ra(镭牌)后,立刻拉着基友小 A 到了一家……餐馆,很低端的那种。
uim 指着墙上的价目表(太低级了没有菜单),说:“随便点”。
题目描述
不过 uim 由于买了一些书,口袋里只剩 M M M 元 ( M ≤ 10000 ) (M \le 10000) (M≤10000)。
餐馆虽低端,但是菜品种类不少,有 N N N 种 ( N ≤ 100 ) (N \le 100) (N≤100),第 i i i 种卖 a i a_i ai 元 ( a i ≤ 1000 ) (a_i \le 1000) (ai≤1000)。由于是很低端的餐馆,所以每种菜只有一份。
小 A 奉行“不把钱吃光不罢休”,所以他点单一定刚好把 uim 身上所有钱花完。他想知道有多少种点菜方法。
由于小 A 肚子太饿,所以最多只能等待 1 1 1 秒。
输入格式
第一行是两个数字,表示 N N N 和 M M M。
第二行起 N N N 个正数 a i a_i ai(可以有相同的数字,每个数字均在 1000 1000 1000 以内)。
输出格式
一个正整数,表示点菜方案数,保证答案的范围在 int 之内。
样例 #1
样例输入 #1
4 4
1 1 2 2
样例输出 #1
3
提示
2020.8.29,增添一组 hack 数据 by @yummy
解题思路
根据题目,每个菜品只有一份balabala,得出这是01背包变式,只不过dp数组存储的东西变成了方案数。
那么,我们遍历每一道菜品时,只需要在吃 不吃之间选择。
如果不吃:延续上一个菜品的方案数
如果吃:套用01背包公式,还要再加上当前钱数-菜品钱数的方案数。
得到状态转移方程: d p [ i ] [ j ] + = d p [ i − 1 ] [ j − a r r [ i ] ] dp[i][j]+=dp[i-1][j-arr[i]] dp[i][j]+=dp[i−1][j−arr[i]]
AC代码
#include<iostream>using namespace std;
int arr[105];
int dp[105][10005];int main()
{int n,m;cin>>n>>m;for(int i=1;i<=n;i++){cin>>arr[i];dp[i][0]=1;//选一个的话都有1种选法。 }dp[0][0]=1;//initfor(int i=1;i<=n;i++){for(int j=1;j<=m;j++){dp[i][j] += dp[i-1][j];//先都按照吃不起算 if(j >= arr[i])//如果吃得起 {dp[i][j]+=dp[i-1][j-arr[i]];//转换为01背包问题 }}}cout<<dp[n][m];
}
普及/提高-
P1434 滑雪
题目描述
Michael 喜欢滑雪。这并不奇怪,因为滑雪的确很刺激。可是为了获得速度,滑的区域必须向下倾斜,而且当你滑到坡底,你不得不再次走上坡或者等待升降机来载你。Michael 想知道在一个区域中最长的滑坡。区域由一个二维数组给出。数组的每个数字代表点的高度。下面是一个例子:
1 2 3 4 5
16 17 18 19 6
15 24 25 20 7
14 23 22 21 8
13 12 11 10 9
一个人可以从某个点滑向上下左右相邻四个点之一,当且仅当高度会减小。在上面的例子中,一条可行的滑坡为 24 − 17 − 16 − 1 24-17-16-1 24−17−16−1(从 24 24 24 开始,在 1 1 1 结束)。当然 25 25 25- 24 24 24- 23 23 23- … \ldots …- 3 3 3- 2 2 2- 1 1 1 更长。事实上,这是最长的一条。
输入格式
输入的第一行为表示区域的二维数组的行数 R R R 和列数 C C C。下面是 R R R 行,每行有 C C C 个数,代表高度(两个数字之间用 1 1 1 个空格间隔)。
输出格式
输出区域中最长滑坡的长度。
样例 #1
样例输入 #1
5 5
1 2 3 4 5
16 17 18 19 6
15 24 25 20 7
14 23 22 21 8
13 12 11 10 9
样例输出 #1
25
提示
对于 100 % 100\% 100% 的数据, 1 ≤ R , C ≤ 100 1\leq R,C\leq 100 1≤R,C≤100。
解题思路
这是一道dfs的问题,为了防止数据爆,所以加一个记忆化搜索。
单独说思路的话……不太好说啊,直接放一下代码吧。
这里主要是取max的东西比较容易晕,需要着重记忆一下。剩下的就是dfs模板啦
AC代码
#include<bits/stdc++.h>
using namespace std;
const int N = 105;int arr[N][N],dp[N][N];
int ne[4][2] = {0,1,1,0,0,-1,-1,0};//可以到达的四个位置 int n,m;int dfs(int x,int y)
{if(dp[x][y] != 0) return dp[x][y];for(int i=0;i<4;i++){int nx = x+ne[i][0];int ny = y+ne[i][1];if(nx < 1 || nx > n || ny < 1 || ny > m || arr[nx][ny] >= arr[x][y]) continue;//边界条件 dp[x][y] = max(dfs(nx,ny)+1,dp[x][y]);//原有的路径长和dfs路径长+1(因为加上它本身)取最大值 }return max(dp[x][y],1);//不可以是0 }int main()
{cin>>n>>m;for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){cin>>arr[i][j];}}int res = 0;for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){res = max(res,dfs(i,j)); //设置变量res每一次找最大值 }}cout<<res;}
普及+/提高
更多推荐
洛谷题单题解【动态规划1】
发布评论