抱歉，您的浏览器无法访问本站
本页面需要浏览器支持（启用）JavaScript
了解详情 >

一方の笔记本

The only source of knowledge is experience.

博客

随笔

朋友

归档

关于

算法分析与设计第四次作业题题解

算法学习题解课业

发布于：2021年10月24日

题目发布于2021年10月25日下午5点。

本次题目主要都是动态规划，A题和B题都是换汤不换药的0-1背包问题，C题是求最大递增、递减子序列，D题是很基础的路径问题，E题也很易得递推方程。

Problem A

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include <bits/stdc++.h>
using namespace std;
int main() {
	ios::sync_with_stdio(false);
	int T, M;
	cin >> T >> M;
	vector<int>cost(M + 1), value(M + 1);
	for (int i = 1; i <= M; i++) {
		cin >> cost[i] >> value[i];
	}
	vector<vector<int>>dp(M + 1, vector<int>(T + 1, 0));
	for (int i = 1; i <= M; i++) {//最好外层是物品件数
		for (int j = T; j >= cost[i]; j--) {//内层是cost，此时顺向、逆向枚举均可
			dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - cost[i]] + value[i]);
		}
	}
	cout << dp[M][T] << endl;
	return 0;
}

Problem B

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <bits/stdc++.h>
using namespace std;
int main() {
	ios::sync_with_stdio(false);
	int V, M;
	cin >> V >> M;
	vector<int>cost(M + 1), value(M + 1);
	for (int i = 1; i <= M; i++) {
		cin >> cost[i];
		value[i] = cost[i];
	}
	vector<vector<int>>dp(M + 1, vector<int>(V + 1, 0));
	for (int i = 1; i <= M; i++) {
		for (int j = V; j >= cost[i]; j--) {
			dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - cost[i]] + value[i]);
		}
	}
	cout << V - dp[M][V] << endl;
	return 0;
}

此外，0-1背包问题还可以进行空间的优化。 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include <bits/stdc++.h>
using namespace std;
int main() {
	ios::sync_with_stdio(false);
	int T, M;
	cin >> T >> M;
	vector<int>cost(M + 1), value(M + 1);
	for (int i = 1; i <= M; i++) {
		cin >> cost[i] >> value[i];
	}
	vector<int>dp(T + 1, 0);
	for (int i = 1; i <= M; i++) {
		for (int j = T; j >= cost[i]; j--) {//注意压缩空间后必须逆向枚举j
			dp[j] = max(dp[j], dp[j - cost[i]] + value[i]);
		}
	}
	cout << dp[T] << endl;
	return 0;
}

多重背包问题、完全背包问题与0-1背包问题类似。

多重背包问题代码如下。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <bits/stdc++.h>
using namespace std;
int main() {
	ios::sync_with_stdio(false);
	int V, M;
	cin >>V >> M;
	vector<int>cost(M + 1), value(M + 1), nums(M + 1);
	for (int i = 1; i <= M; i++) {
		cin >> cost[i] >> value[i] >> nums[i];
	}
	vector<vector<int>>dp(M + 1, vector<int>(V + 1, 0));
	for (int i = 1; i <= M; i++) {
		for (int j = cost[i]; j <= V; j++) {
			for (int k = 0; j >= k * cost[i] && k <= nums[i]; k++) {
				dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - k * cost[i]] + k * value[i]);
			}
		}
	}
	cout << dp[M][V] << endl;
	return 0;
}

完全背包问题代码如下。

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
#include <bits/stdc++.h>
using namespace std;
int main() {
	ios::sync_with_stdio(false);
	int V, M;
	cin >>V >> M;
	vector<int>cost(M + 1), value(M + 1);
	for (int i = 1; i <= M; i++) {
		cin >> cost[i] >> value[i];
	}
	vector<vector<int>>dp(M + 1, vector<int>(V + 1, 0));
	for (int i = 1; i <= M; i++) {
		for (int j = cost[i]; j <= V; j++) {
			for (int k = 0; j >= k * cost[i]; k++) {
				dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - k * cost[i]] + k * value[i]);
			}
		}
	}
	/*或者可以这样
	for (int i = 1; i <= M; i++) {
		for (int j = cost[i]; j <= V; j++) {
			dp[i][j] = max(dp[i - 1][j], dp[i][j - cost[i]] + value[i]);
			//与0-1背包问题的唯一不同就是后一项中dp那部分的下标由(i - 1, j - cost[i])变为了(i, j - cost[i])
		}
	}
	*/
	cout << dp[M][V] << endl;
	return 0;
}

Problem C

题目描述

\(N\)位同学站成一排，音乐老师要请其中的\((N-K)\)位同学出列，使得剩下的\(K\)位同学排成合唱队形。 合唱队形是指这样的一种队形：设\(K\)位同学从左到右依次编号为\(1,2,...,K\)，他们的身高分别为\(T_1,T_2,...,T_K\)，则他们的身高满足\(T_1<...<T_i\)且\(T_i> T_{i+1}>...>T_K(1 \leq i \leq K)\)。 你的任务是，已知所有N位同学的身高，计算最少需要几位同学出列，可以使得剩下的同学排成合唱队形。

题解

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
#include<bits/stdc++.h>
using namespace std;
int main() {
	int N;
	cin >> N;
	int K = 0;
	vector<int> T(1, -1);
	//第i位同学左侧最长单调增子序列、右侧最长单调减子序列的长度
	for (int i = 0; i < N; i++) {
		int Ti;
		cin >> Ti;
		T.emplace_back(Ti);
	}
	vector<int> dp_l(N + 1, 0), dp_r(N + 1, 0);
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j < i; j++) {
			if (T[i] > T[j]) {
				dp_l[i] = max(dp_l[i], dp_l[j] + 1);
			}
		}
	}
	for (int i = N; i >= 1; i--) {
		for (int j = N; j > i; j--) {
			if (T[i] > T[j]) {
				dp_r[i] = max(dp_r[i], dp_r[j] + 1);
			}
		}
	}
	for (int i = 1; i <= N; i++) {
		K = max(K, dp_l[i] + dp_r[i] + 1);
	}
	cout << N - K << endl;
	return 0;
}

Problem D

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
#include <bits/stdc++.h>
using namespace std;
int m, n, x, y;
bool valid(int i, int j){
	return !((i == x && j == y) || ((x - i) * (x - i) + (y - j) * (y - j) == 5));
}
int main() {
	ios::sync_with_stdio(false);
	cin >> n >> m >> x >> y;//卒要从(0, 0)到(n, m)，马在(x, y)处不会动，马所能一步到达的位置和马自身的位置设定为不可达，卒只能向右或向下走，每次一步
	vector<vector<int>> dp(n + 1, vector<int>(m + 1, 0));
	dp[0][0] = valid(0, 0) ? 1 : 0;
	for(int i = 0; i <= n; i++) {
		for (int j = 0; j <= m; j++) {
			if (i + j && valid(i, j)) {
				if (i == 0) {
					dp[i][j] += dp[i][j - 1];
				}
				else if (j == 0) {
					dp[i][j] += dp[i - 1][j];
				}
				else {
					dp[i][j] += dp[i - 1][j];
					dp[i][j] += dp[i][j - 1];
				}
			}
		}
	}
	cout << dp[n][m] << endl;
	return 0;
}

Problem E

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include <bits/stdc++.h>
using namespace std;
int main() {
	ios::sync_with_stdio(false);
	int n, m;
	cin >> n >> m;//n人传球m次，只能传给编号相邻的同学，从1号开始发球，求有多少种传球方法最后球能回到1号同学手里；注意1->2算一次传球
	vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));
	dp[0][1] = 1;//dp[i][j]代表第i次传到编号为j的同学处的方法数
	for (int i = 1; i <= m; i++) {
		for (int j = 1; j <= n; j++) {
			int l = j > 1 ? j - 1 : n;
			int r = j < n ? j + 1 : 1;
			dp[i][j] = dp[i - 1][l] + dp[i - 1][r];
		}
	}
	cout << dp[m][1] << endl;
	return 0;
}

评论