动态规划习题
[USACO1.5] [IOI1994]数字三角形 Number Triangles
题目描述
观察下面的数字金字塔。
写一个程序来查找从最高点到底部任意处结束的路径，使路径经过数字的和最大。每一步可以走到左下方的点也可以到达右下方的点。
在上面的样例中，从 $7 \to 3 \to 8 \to 7 \to 5$ 的路径产生了最大权值。
输入格式
第一个行一个正整数 $r$ ,表示行的数目。
后面每行为这个数字金字塔特定行包含的整数。
输出格式
单独的一行,包含那个可能得到的最大的和。
样例 #1
样例输入 #1
1 | 5 |
样例输出 #1
1 | 30 |
提示
【数据范围】
对于 $100\%$ 的数据，$1\le r \le 1000$，所有输入在 $[0,100]$ 范围内。
题目翻译来自NOCOW。
USACO Training Section 1.5
IOI1994 Day1T1
题解
思路
记忆化搜索：
mem存储重复的。
DP；
状态转化方程：f[i][j]=max(f[i+1][j],f[i+1][j+1])+g[i][j];要倒着推。因为dfs递归时候是正着推的。
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
using namespace std;
const int N=1010;
int n;
int g[N][N];
int mem[N][N];
int f[N][N];
int dfs(int x,int y) {
if(mem[x][y]) return mem[x][y];
int sum=0;
if(x>n||y>n) return 0;
//求最优子问题 dfs(x)=max(dfs(x+1),dfs(x+2));
//求子问题的和 dfs(x)=dfs(x+1)+dfs(x+2);
else sum=max(dfs(x+1,y),dfs(x+1,y+1))+g[x][y];
mem[x][y]=sum;
return sum;
}
int main() {
scanf("%d",&n);
for(int i=1; i<=n; i++) {
for(int j=1; j<=i; j++) {
scanf("%d",&g[i][j]);
}
}
for(int i=n; i>=1; i--) {
for(int j=1; j<=n; j++) {
f[i][j]=max(f[i+1][j],f[i+1][j+1])+g[i][j];
}
}
printf("%d\n",f[1][1]);
return 0;
}
1 |
|
[NOIP1999 提高组] 导弹拦截
题目描述
某国为了防御敌国的导弹袭击，发展出一种导弹拦截系统。但是这种导弹拦截系统有一个缺陷：虽然它的第一发炮弹能够到达任意的高度，但是以后每一发炮弹都不能高于前一发的高度。某天，雷达捕捉到敌国的导弹来袭。由于该系统还在试用阶段，所以只有一套系统，因此有可能不能拦截所有的导弹。
输入导弹依次飞来的高度，计算这套系统最多能拦截多少导弹，如果要拦截所有导弹最少要配备多少套这种导弹拦截系统。
输入格式
一行，若干个整数，中间由空格隔开。
输出格式
两行，每行一个整数，第一个数字表示这套系统最多能拦截多少导弹，第二个数字表示如果要拦截所有导弹最少要配备多少套这种导弹拦截系统。
样例 #1
样例输入 #1
1 | 389 207 155 300 299 170 158 65 |
样例输出 #1
1 | 6 |
提示
对于前 $50\%$ 数据（NOIP 原题数据），满足导弹的个数不超过 $10^4$ 个。该部分数据总分共 $100$ 分。可使用$\mathcal O(n^2)$ 做法通过。
对于后 $50\%$ 的数据，满足导弹的个数不超过 $10^5$ 个。该部分数据总分也为 $100$ 分。请使用 $\mathcal O(n\log n)$ 做法通过。
对于全部数据，满足导弹的高度为正整数，且不超过 $5\times 10^4$。
此外本题开启 spj，每点两问，按问给分。
NOIP1999 提高组 第一题
$\text{upd 2022.8.24}$：新增加一组 Hack 数据。
题解
思路
这道题有两问：一个是求这套拦截系统最多能拦截多少导弹，另一个是求拦截所有导弹最少要配备多少套这种导弹拦截系统。
第一问：我们需要的是求一个系统最多能拦截多少导弹，那么我们需要遍历输入的数组，当遍历到的导弹比前面的小，那么它就认它为老大，用同一套系统，下标+1，往后排。如果没有比它大的，那么它就单独用一套系统。以此类推，往后遍历。
第二问：我们需要的是求拦截所有导弹最少需要几个系统，那么我们需要遍历输入的数组，当遍历的导弹比前面大，则需要换一个系统，因此可以求得最少的系统数
这是贪心的思想，先求出单个小的最优往上推。
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
using namespace std;
int n,t,ans=1,a[100010],d[100010],f[100010];
//a[]存储的是输入的数
//f[]存储的是系统能拦截最多的导弹的下标或最少用几个系统的下标（即输出结构）
//d[]存储的是当前值的前面最大的那一个的下标
//t存储的是前面的下标
int main() {
while(scanf("%d",&a[++n])!=EOF);
n--;
for(int i=1; i<=n; i++) {
f[i]=1;//将输入的数据的下标都改成1，方便后面同一系统+1
for(int j=t; j>0; j--) {//从后往前找
if(a[i]<=a[d[j]]) { //如果前面有比这个数大的，就跟着前面的系统
f[i]=f[d[j]]+1;//在系统的排序+1，上述下标+1,d[]是最后一个导弹对应的标号
break;
}
}
t=max(t,f[i]);//选择下一个最后一个导弹前的最大下标值，就是为了方便查找
d[f[i]]=i;//其实是为了方便遍历下一个值
ans=max(ans,f[i]);
}
cout<<ans<<endl;
ans=1;
t=0;
for(int i=1;i<=n;i++){
f[i]=1;
for(int j=t;j>0;j--){
if(a[i]>a[d[j]]){ //如果前面有比这个数小，那么下标+1，目的是为了区分系统，使得选用的系统最少
f[i]=f[d[j]]+1;
break;
}
}
t=max(t,f[i]);
d[f[i]]=i;
ans=max(ans,f[i]);
}
cout<<ans;
return 0;
}
1 |
|
01背包问题
题目描述
有N件物品和一个容量是 V的背包。每件物品只能使用一次。
第i件物品的体积是 vi，价值是 wi。
求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值大。输出最大价值。
输入格式
第一行两个整数，N，V，用空格隔开，分别表示物品数量和背包容积。
接下来有 N行，每行两个整数 vi,wi，用空格隔开，分别表示第 i件物品的体积和价值。
输出格式
输出一个整数，表示最大价值。
数据范围
0<N,V<=1000
0<vi,wi≤1000
输入样例
1 | 4 5 |
输出样例：
1 | 8 |
题解
思路
先画出二叉搜索树，按背包体积去选择，从第一个开始，初始背包体积为5，然后往后遍历，每次遍历有两种选择：
1.不选分两种情况：
（1）背包体积不够装下当前物品，也就是当前物品的体积大于背包剩余体积。
（2）背包体积够，但是不想选。
2.选
选的话，背包体积需要减去该物品的体积，然后要加上物品的价值。
dp的话需要从下往上遍历，那么底部序号i从m开始遍历到1，而体积从1（或0）开始遍历到m。
如果从上往下推dp的话，
代码
1 |
|
1 | //空间优化 |
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
//继续优化空间
using namespace std;
const int N=1010;
int n,m;
int v[N],w[N];
int f[N];
int main() {
scanf("%d %d",&n,&m);
for(int i=1; i<=n; i++) {
scanf("%d %d",&v[i],&w[i]);
}
for(int i=1;i<=n;i++){
for(int j=m;j>=0;j--){
if(j>=v[i])
f[j]=max(f[j],f[j-v[i]]+w[i]);
}
}
printf("%d",f[m]);
return 0;
}
1 | //继续优化空间 |
二维费用的背包问题
题目详细
有 N件物品和一个容量是 V的背包，背包能承受的最大重量是 M。
每件物品只能用一次。体积是 vi，重量是 mi，价值是 wi。
求解将哪些物品装入背包，可使物品总体积不超过背包容量，总重量不超过背包可承受的最大重量，且价值总和最大。输出最大价值。
输入格式
第一行三个整数，N,V,M，用空格隔开，分别表示物品件数、背包容积和背包可受的最大重量。
接下来有 N行，每行三个整数 vi,mi,wi，用空格隔开，分别表示第 i件物品的体积、重量和价值。
输出格式
输出一个整数，表示最大价值。
数据范围
0<N≤1000
0<V,M≤100
0<vi,mi≤100
0<wi≤1000
输入样例
1 | 4 5 6 |
输出样例：
1 | 8 |
题解
思路
这题有两个限制条件，一个是背包的体积，另一个是背包的重量。
dp的思想是每次枚举到的序号，它有选和不选两种情况，当选的时候，
即背包体积大于当前物品体积且背包重量没有超过M。那么输出最大的价值为前一个价值或者当前价值两者中最大的那一个。
降维：参考01背包的第二个空间优化。注意要倒序，否则可能出现物品拿两次的情况。
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
using namespace std;
const int N=1010;
int n,V,M;
int v[N],m[N],w[N];
int f[110][110];
int main(){
scanf("%d %d %d",&n,&V,&M);
for(int i=1;i<=n;i++){
scanf("%d %d %d",&v[i],&m[i],&w[i]);
}
for(int i=1;i<=n;i++){
for(int j=V;j>=v[i];j--){
for(int k=M;k>=m[i];k--){
f[j][k]=max(f[j][k],f[j-v[i]][k-m[i]]+w[i]);
}
}
}
printf("%d\n",f[V][M]);
return 0;
}
1 |
|
完全背包问题
题目详解
有 N种物品和一个容量是 V的背包，每种物品都有无限件可用。
第 i种物品的体积是 vi，价值是 wi。
求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。输出最大价值。
输入格式
第一行两个整数，N，V，用空格隔开，分别表示物品种数和背包容积。
接下来有 N 行，每行两个整数 vi,wi，用空格隔开，分别表示第 i种物品的体积和价值。
输出格式
输出一个整数，表示最大价值。
数据范围
0<N,V≤1000
0<vi,wi≤1000
输入样例
1 | 4 5 |
输出样例：
1 | 10 |
题解
思路
完全背包问题与01背包问题的区别是，完全背包每次能重复拿，而01背包每次每个物品只能拿一个。
代码
1 |
|
[NOIP2005 普及组] 采药
题目描述
辰辰是个天资聪颖的孩子，他的梦想是成为世界上最伟大的医师。为此，他想拜附近最有威望的医师为师。医师为了判断他的资质，给他出了一个难题。医师把他带到一个到处都是草药的山洞里对他说：“孩子，这个山洞里有一些不同的草药，采每一株都需要一些时间，每一株也有它自身的价值。我会给你一段时间，在这段时间里，你可以采到一些草药。如果你是一个聪明的孩子，你应该可以让采到的草药的总价值最大。”
如果你是辰辰，你能完成这个任务吗？
输入格式
第一行有 $2$ 个整数 $T$（$1 \le T \le 1000$）和 $M$（$1 \le M \le 100$），用一个空格隔开，$T$ 代表总共能够用来采药的时间，$M$ 代表山洞里的草药的数目。
接下来的 $M$ 行每行包括两个在 $1$ 到 $100$ 之间（包括 $1$ 和 $100$）的整数，分别表示采摘某株草药的时间和这株草药的价值。
输出格式
输出在规定的时间内可以采到的草药的最大总价值。
样例 #1
样例输入 #1
1 | 70 3 |
样例输出 #1
1 | 3 |
提示
【数据范围】
- 对于 $30\%$ 的数据，$M \le 10$；
- 对于全部的数据，$M \le 100$。
【题目来源】
NOIP 2005 普及组第三题
题解
思路
简单的01背包问题，套公式。注意数组别开太小，不然跑不过去
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
using namespace std;
const int N=110;
int T,m;
int t[N],w[N];
int f[1010];
int main(){
scanf("%d %d ",&T,&m);
for(int i=1;i<=m;i++){
scanf("%d %d",&t[i],&w[i]);
}
for(int i=1;i<=m;i++){
for(int j=T;j>=0;j--){
if(j>=t[i])
f[j]=max(f[j],f[j-t[i]]+w[i]);
}
}
printf("%d",f[T]);
return 0;
}
1 |
|
[NOIP2006 普及组] 开心的金明
题目描述
金明今天很开心，家里购置的新房就要领钥匙了，新房里有一间他自己专用的很宽敞的房间。更让他高兴的是，妈妈昨天对他说：“你的房间需要购买哪些物品，怎么布置，你说了算，只要不超过 $N$ 元钱就行”。今天一早金明就开始做预算，但是他想买的东西太多了，肯定会超过妈妈限定的 $N$ 元。于是，他把每件物品规定了一个重要度，分为 $5$ 等：用整数 $1-5$ 表示，第 $5$ 等最重要。他还从因特网上查到了每件物品的价格（都是整数元）。他希望在不超过 $N$ 元（可以等于 $N$ 元）的前提下，使每件物品的价格与重要度的乘积的总和最大。
设第$j$件物品的价格为 $v_j$，重要度为 $w_j$，共选中了 $k$ 件物品，编号依次为 $j_1,j_2,…,j_k$，则所求的总和为：
$v{j_1} \times w{j1}+v{j2} \times w{j2} …+v{jk} \times w{j_k}$。
请你帮助金明设计一个满足要求的购物单。
输入格式
第一行，为 $2$ 个正整数，用一个空格隔开：$n,m$（$n<30000,m<25$）其中 $n$ 表示总钱数，$m$ 为希望购买物品的个数。
从第 $2$ 行到第 $m+1$ 行，第 $j$ 行给出了编号为 $j-1$ 的物品的基本数据，每行有 $2$ 个非负整数 $v,p$（其中 $v$ 表示该物品的价格 $(v \le 10000)$，$p$ 表示该物品的重要度（$1\le p\le5$）。
输出格式
$1$ 个正整数，为不超过总钱数的物品的价格与重要度乘积的总和的最大值（$<100000000$）。
样例 #1
样例输入 #1
1 | 1000 5 |
样例输出 #1
1 | 3900 |
提示
NOIP 2006 普及组 第二题
题解
思路
01背包问题，然后再优化空间就好了。注意将重要度要转化成重要度和价格的乘积
代码
1 |
|
