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

动态规划的题目。

个人认为学习动态规划更容易理解的学习路径为暴力搜索\(\Rightarrow\)记忆化搜索优化\(\Rightarrow\)动态规划。

Problem A

题目描述

给定\(1×N\)的单行矩阵，矩阵每个元素都是\(-127\)到\(127\)之间的整数。请找到一个连续子矩阵，使得其元素之和最大。

输入数据

多组测试数据，每组数据的第一行为一个整数\(N(N \leq 100)\)，第二行包含\(N\)个整数，为行矩阵的\(N\)个元素，每个元素介于\(-127\)到\(127\)之间。

输出数据

最大子矩阵之和，每组对应一行。

样例输入

1 2	10 0 -2 -7 0 -2 11 -4 13 -5 -2

样例输出

题目分析

求最大连续子序列之和的题目。

题解

#include <bits/stdc++.h>
using namespace std;
int main() {
	int N;
	while (cin >> N) {
		vector<int> nums(N);
		for (auto& i : nums) {
			cin >> i;
		}
		vector<int> dp(N, INT_MIN);
		int ans = INT_MIN;
		dp[0] = nums[0];
		for (int i = 1; i < N; i++) {
			dp[i] = max(dp[i - 1] + nums[i], nums[i]);
			ans = max(ans, dp[i]);
		}
		cout << ans << endl;
	}
	return 0;
}

Problem B

题目描述

给定\(N×N\)矩阵，矩阵元素都是\(-127\)到\(127\)之间的整数。请找到一个子矩阵，使得其元素之和最大。

输入数据

多组测试数据，每组测试数据的第一行整数\(N (N \leq 100)\)；接下来N行元素，每行N个元素，每个元素介于\(-127\)到\(127\)之间。

输出数据

最大子矩阵元素之和，每组测试数据对应一行。

样例输入

样例输出

题目分析

思想与A题类似，本题对输入的矩阵进行列的求和，然后用\(i\)和\(j\)对行进行遍历\((1 \leq i \leq j \leq N)\)，然后对于确定的\(i\)和\(j\)，使用\(k\)进行列的遍历，最后求出最大的结果即可。

题解

#include <bits/stdc++.h>
using namespace std;
int main() {
	int N;
	ios::sync_with_stdio(false);
	cin.tie(0);
	while (cin >> N) {
		vector<vector<int>> nums(N + 1, vector<int>(N + 1));
		for (int i = 1; i <= N; i++) {
			for (int j = 1; j <= N; j++) {
				cin >> nums[i][j];
			}
		}
		vector<vector<int>> dp(N + 1, vector<int>(N + 1, INT_MIN));
		for (int i = 1; i <= N; i++) {
			for (int j = 1; j <= N; j++) {
				dp[i][j] = dp[i - 1][j] + nums[i][j];
			}
		}
		int ans = nums[0][0];
		for (int i = 1; i <= N; i++) {
			for (int j = i; j <= N; j++) {
				int _sum = 0;
				for (int k = 1; k <= N; k++) {
					_sum = max(dp[j][k] - dp[i - 1][k] + _sum, dp[j][k] - dp[i - 1][k]);
					ans = max(ans, _sum);
				}
			}
		}
		cout << ans << endl;
	}
	return 0;
}

Problem C

题目描述

作为一个有很多游戏想买但囊中羞涩的大学生，小明决定在这个暑假开始打工赚钱。经过一段时间的寻找，他一共找到了\(n\)个打工的招聘广告，其中第\(i\)个打工的日期从\(l_i\)开始，到\(r_i\)为止，一共付给他\(c_i\)元钱。因为这些打工的时间都相互冲突，所以同一天小明最多参加一个打工，并且一个打工一旦开始，就必须一直工作到结束，不能中途退出。现在小明想要知道，这个暑假他打工最多能得到多少钱？

输入数据

第一行一个整数\(n(1 \leq n \leq 1000000)\)，表示招聘广告的数量；接下来一共\(n\)行，每行3个整数\(l_i,r_i,c_i(1 \leq l_i ≤ r_i \leq 1000000,1 \leq c_i \leq 1000000000)\)，表示打工的开始时间，结束时间和报酬。

输出数据

一行一个整数\(k\)，表示小明最多能够得到的钱数。

样例输入

样例输出

题目分析

基本思路

这题目的思路可以从LintCode 515题中得到一些启发。如果采用动态规划的话，对于\(n\)项工作而言，每一项工作只有选和不选两种情况，设\(dp[i][0]、dp[i][1]\)为第\(i\)件工作接受或者不接受的条件下所获得的最大酬劳，那么最终的答案为\(max(dp[n][0],dp[n][1])\)。

但是本题对于每项工作的选择是有后效性的，必须要满足时间的约束条件；而要使得获得的薪酬最大，应该尽可能多做一些工作。根据会场安排的问题可以想到应该按照工作的结束时间进行排序。

会场安排问题

假设某社团某一天要组织\(𝑛\)个活动\(𝐸=\begin{Bmatrix}1, 2,⋯,n\end{Bmatrix}\)，其中每个活动都要求使用同一礼堂，而且在同一时间内只有一个活动能使用这个礼堂。每个活动\(i\)都有一个要求使用礼堂的起始时间\(s_i\)和结束时间\(f_i\)，且有\(s_i < f_i\)。如果选择了活动\(i\)，则它在半开时间区间\([s_i,f_i)\)内占用资源。若区间\([s_i,f_i)\)与区间\([s_j,f_j)\)不相交，则称活动\(i\)与活动\(j\)是相容的。现在给定𝑛个活动的开始时间和结束时间，请设计一个活动安排方案，使得安排的相容活动数目最多。

分析题目，要解决这个问题可以使用二进制枚举，但是时间复杂度是\(O(2^n)\)，不可以接受，因此换一个思路。使用贪心的策略大致有三个思路：

按照占用时间短优先；
按照开始时间早优先；
按照结束时间早优先。

对于前两种情况，都可以找出反例证明贪心算法不成立：对于按照占用时间短优先的方案，反例为\([0,10),[9,14),[13,17)\)，按照占用时间短优先的话应该先安排\([9,14)\)，而最优安排显然是选另外两个；对于按照开始时间早优先的方案，反例为\([0,10),[2,5),[6,7)\)，显然。那么如何证明按照结束时间早的贪心策略是正确的呢？

将集合\(S\)中的活动按照结束时间递增顺序排列，即记为\(S=\begin{Bmatrix}1,2,⋯,n \end{Bmatrix}\)；假设\(A=\begin{Bmatrix}j_1,j_2,...,j_m \end{Bmatrix}\)是\(S\)的一个最优解，其中活动也按照结束时间递增顺序排列。不妨设\(B=\begin{Bmatrix}A_1,A_2,⋯,A_c \end{Bmatrix}\)为该问题的最佳解构成的集合，显然对于任意一个有限的会场安排问题，总是存在最优解。现在需要证明对于贪心算法得出的这样的解\(A\)总满足\(A \in B\)。

设\(k=1\)时选择活动为\(\begin{Bmatrix}1\end{Bmatrix}\)，需要证明存在一个最优解包含\(\begin{Bmatrix}1\end{Bmatrix}\)，若\(j_1=1\)，那么最优解包含了\(\begin{Bmatrix}1\end{Bmatrix}\)；否则，用活动\(1\)替换最优解中的\(j_1\)，显然\(A'=\begin{Bmatrix} 1,j_2,...,j_m \end{Bmatrix}\)也是一个相容的活动集合（\(1\)是结束时间最早的活动），也是一个最优的活动安排。

当\(k>1\)时，设\(\{ i_1,1_2,...,i_k \}\)是贪心算法前\(k\)步顺序选择的活动，那么存在一个最优解:\(A=\{ i_1=1,1_2,...,i_k \} \bigcup B\)。假设\(S'\)是\(S\)中与\(\{ i_1, i_2,⋯,i_k \}\)相容的活动，即\(S'=\{ j | s[j]≥𝑓[i_k], j \in 𝑆 \}\)，那么\(B\)是\(S'\)的一个最优解。再用刚才关于活动\(1\)的替换等价性证明可知\(𝑆'\) 的结束时间最早的活动\(𝑖_{𝑘+1}\)包含在某一个最优解\(B'\)中，则可以构造原问题的一个最优解为\(A'=\{ i_1=1,1_2,...,i_k,i_{k+1} \} \bigcup (B - \{ i_{k+1} \})\)。

最终的代码如下所示。

#include <bits/stdc++.h>
using namespace std;
struct activity {
	int start;
	int end;
	bool operator<(const activity& b) const{
		return end < b.end;
	}
};
int main() {
	int n;
	cin >> n;
	if (n < 1) {
		return 0;
	}
	vector<activity> act(n);
	for (auto& i : act) {
		cin >> i.start >> i.end;
	}
	sort(act.begin(), act.end());
	int ans = 1;//选择第一个活动
	int last_selected = 0;
	for (int i = 1; i < n; i++) {
		if (act[i].start >= act[last_selected].end) {
			last_selected = i;
			ans++;
		}
	}
	cout << ans << endl;
	return 0;
}
/*
测试用例1（答案为2）
3
0 10
2 5
7 9
测试用例2（答案为2）
3
0 4
3 5
4 9
*/

网上查找了资料后发现本题或许可以使用树状数组来解决。

树状数组

树状数组可以解决大部分基于区间上的更新以及求和问题。设结点编号为\(x\)，那么该节点维护的值为\((x-\text{lowbit}(x),x]\)的和，其中\(\text{lowbit}(x)=x^k\)，其中\(k\)为\(x\)最低位1所在的二进制位。这种情况下要求树状数组的编号范围是\([1,2^n]\)。

\(\text{lowbit}\)值一般使用\(x \& (-x)\)的方式计算，这一点利用了补码的运算性质，证略。

本题目使用树状数组进行了工作结束日期的统计。最后改完代码后发现用 vector 空间会爆掉，所以直接使用空间足够大的数组即可。

题解

#include <bits/stdc++.h>
#define MAX_SIZE 1000005
using ll = long long;
using namespace std;
struct adver {
	int start;
	int end;
	int income;
};

ll dp[MAX_SIZE][2];
ll temp[MAX_SIZE];
adver adver_info[MAX_SIZE];

int lowbit(int i) {
	return i & (-i);
}

int sum(int i) {//统计结束日期小于i的工作数量
	int s = 0;
	while (i > 0) {
		s += temp[i];
		i -= lowbit(i);
	}
	return s;
}

void add(int i) {//添加一个结束日期为i的工作
	if (i > 0){
	while (i < MAX_SIZE) {
			temp[i]++;
			i += lowbit(i);
		}
	}
}

bool cmp(adver& a, adver& b) {//排序依据
	return a.end < b.end;
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	int n;
	cin >> n;
	ll ans = 0;
	for (int i = 1; i <= n; i++) {
		cin >> adver_info[i].start >> adver_info[i].end >> adver_info[i].income;
	}
	sort(adver_info + 1, adver_info + n + 1, cmp);
	//sort(adver_info + 1, adver_info + n + 1, [](adver& a, adver& b) { return a.end < b.end; });
	//sort(adver_info + 1, adver_info + n + 1, comparator(adver, end));
	for (int i = 1; i <= n; i++) {
		dp[i][0] = max(dp[i - 1][0], dp[i - 1][1]);
		ll s = sum(adver_info[i].start - 1);
		dp[i][1] = max(dp[s][0], dp[s][1]) + adver_info[i].income;
		add(adver_info[i].end);
	}
	ans = max(dp[n][1], dp[n][0]);
	cout << ans << endl;
}

Problem D

题目描述

给定一个信封，最多只允许粘贴\(N\)张邮票，计算在给定\(M(N+M \leq 10)\)种邮票的情况下（假定所有的邮票数量都足够），如何设计邮票的面值，能得到最大\(max\)，使得\(\{1,\dots ,max\}\)的每一个邮资值都能得到？

输入数据

一行，分别为\(N,M\)。

输出数据

第一行为\(m\)种邮票的面值，按升序排列，各数之间用一个空格隔开；第二行为最大值，格式为："MAX=%d" 。

样例输入

3 2

样例输出

1
2

1 3
MAX=7

题目分析

对于已知邮票面值的情况下，可以使用动态规划求出最大的面值；要求出邮票的面值，可以使用深度优先搜索算法。

题解

/*
每次在增加邮票面值时，所需要枚举的空间为上次求得的最大值+1到上一个枚举出来的邮票面值+1，上界很显然，由于邮票面值是要求递增的，因此在求的时候采用递增的策略即可，因此下界选择上一个枚举出来的邮票面值+1
*/
#include <bits/stdc++.h>
using namespace std;
int temp_denomination[15];
int ans_denomination[15];//1~m储存结果
int n, m;//n为最多可贴的邮票数；m为邮票种数
int MAX = 0;

int calculate_MAX(int cur_num) {//计算num个面值的邮票的MAX
    if (cur_num == 0) {
        return 0;
    }
    else {//有点像lintcode749 
        vector<int> dp(1001, INT_MAX);
        dp[0] = 0;
        int i = 0;//面值为1 3   输入为3 2
        if (temp_denomination[1] == 1 && temp_denomination[2] == 3) {
            system("pause");
        }
        while (dp[i] <= n) {//dp[i]总价为i分且面值由cur_num种时、所需要的邮票张数
            i++;
            for (int j = 1; j <= cur_num && temp_denomination[j] <= i; j++) {
                dp[i] = min(dp[i - temp_denomination[j]] + 1, dp[i]);
            }
        }
        return i - 1;
    }
}

void dfs(int cur_num) {
    if (cur_num == m) {//深度优先搜索的最大深度为m，即只需要求出m个面值
        int c = calculate_MAX(m);//利用动态规划计算MAX
        if (c > MAX) {//计算当前所得的MAX值，如果比之前的大就更新MAX与面值
            for (int i = 1; i <= m; i++) {
                ans_denomination[i] = temp_denomination[i];
            }
            MAX = c;
        }
        return;
    }
    else {//没有达到最大深度
        int temp = calculate_MAX(cur_num);//计算当前所得的MAX值
        for (int i = temp + 1; i >= temp_denomination[cur_num] + 1; i--) {//贪心算法的部分
            temp_denomination[cur_num + 1] = i;//往下续，小面值已经不够用了，因此采用temp_MAX + 1
            dfs(cur_num + 1);
        }
    }
}

int main() {
    cin >> n >> m;
    dfs(0);
    cout << ans_denomination[1];
    for (int i = 2; i <= m; i++) {
        cout << " " << ans_denomination[i];
    }
    cout << endl << "MAX=" << MAX << endl;
    return 0;
}

Problem E

题目描述

某国为了防御敌国的导弹袭击，研发出一种导弹拦截系统。但是这种导弹拦截系统有一个缺陷：虽然它的第一发炮弹能够到达任意的高度，但是以后每一发炮弹都不能高于前一发的高度。某天，雷达捕捉到敌国的导弹来袭。由于该系统还在试验阶段，所以只有一套系统，因此有可能不能拦截所有的导弹。

输入数据

输入数据只有一行，该行包含若干个数据，之间用半角逗号隔开，表示导弹依次飞来的高度（导弹最多有\(20\)枚，其高度为不大于\(3×10^3\)的正整数）。

输出数据

输出数据只有一行，该行包含两个数据，之间用半角逗号隔开。第一个数据表示这套系统最多能拦截的导弹数；第二个数据表示若要拦截所有导弹至少要再添加多少套这样的系统。

样例输入

1	389,207,155,300,299,170,158,65

样例输出

6,1

题解

#include <bits/stdc++.h>
using namespace std;
int main() {
	int h;
	char c;
	vector<int> height;
	while (1) {
		cin >> h;
		c = getchar();
		height.emplace_back(h);
		if (c == '\n') {
			break;
		}
	}
	int n = height.size();
	vector<int> dp(n, 1);
	int ans1 = 1;
	for (int i = 1; i < n; i++) {
		for (int j = 0; j < i; j++) {
			if (height[i] < height[j]) {
				dp[i] = max(dp[i], dp[j] + 1);
				ans1 = max(ans1, dp[i]);
			}
		}
	}
	cout << ans1 << ',';
	for (auto& i : dp) {
		i = 1;
	}
	int ans2 = 1;
	for (int i = 1; i < n; i++) {
		for (int j = 0; j < i; j++) {
			if (height[i] > height[j]) {
				dp[i] = max(dp[i], dp[j] + 1);
				ans2 = max(ans2, dp[i]);
			}
		}
	}
	cout << ans2 - 1 << endl;
	return 0;
}

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

Problem A

题目描述

输入数据

输出数据

样例输入

样例输出

题目分析

题解

Problem B

题目描述

输入数据

输出数据

样例输入

样例输出

题目分析

题解

Problem C

题目描述

输入数据

输出数据

样例输入

样例输出

题目分析

基本思路

会场安排问题

树状数组

题解

Problem D

题目描述

输入数据

输出数据

样例输入

样例输出

题目分析

题解

Problem E

题目描述

输入数据

输出数据

样例输入

样例输出

题解

参考资料