夏令营复习算法, 感到自己对之前学过的算法略有生疏, 写篇流水账, 权当复习.
- 最长上升子序列
- 最长公共子序列
- 最大子段和与最大子矩阵
- 背包问题
- 合并石子/矩阵链乘
- 一些其他的题目
最长上升子序列
简单来说, 是通过讨论原序列的当前位 \(a_i\) 与子序列 \(b\) 的末尾 \(b_{len-1}\) 的大小关系进行递推/动态规划的一类问题. 具体思路暂不详述.
实现代码
给定数组 \(a\), 求 \(a\) 某一段 \(a[l, r]\) 的LIS的代码如下:
不严格的情形有两处需要修改, 请仔细查看注释.
1 | // 数组int a[] 的下标从 0 ~ n-1, 函数可求解 [l, r] 闭区间的LIS长度. |
如需求解最长下降子序列, 一个偷懒的办法是将原数组逆序存储, 再求解其逆序的LIS.
同时也有 lower_bound(c, c + len, a[i], greater<int>()) 的用法, 非常方便.
百练 2945: 拦截导弹
总时间限制: 1000ms 内存限制: 65536kB
描述
某国为了防御敌国的导弹袭击，开发出一种导弹拦截系统。但是这种导弹拦截系统有一个缺陷：虽然它的第一发炮弹能够到达任意的高度，但是以后每一发炮弹都不能高于前一发的高度。某天，雷达捕捉到敌国的导弹来袭，并观测到导弹依次飞来的高度，请计算这套系统最多能拦截多少导弹。拦截来袭导弹时，必须按来袭导弹袭击的时间顺序，不允许先拦截后面的导弹，再拦截前面的导弹。
输入
输入有两行，
第一行，输入雷达捕捉到的敌国导弹的数量k（k<=25），
第二行，输入k个正整数，表示k枚导弹的高度，按来袭导弹的袭击时间顺序给出，以空格分隔。
输出
输出只有一行，包含一个整数，表示最多能拦截多少枚导弹。
样例输入
8
300 207 155 300 299 170 158 65
样例输出
6
思路
很裸, 直接做非严格最长下降子序列. 5min内不AC自觉面壁…
AC代码
1 |
|
百练 2711: 合唱队形
题目链接: http://bailian.openjudge.cn/practice/2711/
总时间限制: 1000ms 内存限制: 65536kB
描述
N位同学站成一排，音乐老师要请其中的(N-K)位同学出列，使得剩下的K位同学不交换位置就能排成合唱队形。 合唱队形是指这样的一种队形：设K位同学从左到右依次编号为1, 2, …, K，他们的身高分别为T1, T2, …, TK，则他们的身高满足T1 < T2 < … < Ti , Ti > Ti+1 > … > TK (1 <= i <= K)。 你的任务是，已知所有N位同学的身高，计算最少需要几位同学出列，可以使得剩下的同学排成合唱队形。
输入
输入的第一行是一个整数N（2 <= N <= 100），表示同学的总数。第一行有n个整数，用空格分隔，第i个整数Ti（130 <= Ti <= 230）是第i位同学的身高（厘米）。
输出
输出包括一行，这一行只包含一个整数，就是最少需要几位同学出列。
样例输入
8
186 186 150 200 160 130 197 220
样例输出
4
思路
枚举递增和递减中间分叉的位置（令其位于 \(a_i\) 和 \(a_{i+1}\) 之间, 对 \(i\) 做 for 循环）, 分别对两边做正序和逆序的LIS, 长度相加取最大, 最后再用 \(n\) 减去即可.
注意一个特殊情况, 就是前半段上升的最高点可能和后半段下降的最高点数值相等, 需要特判一下, 然后总长度-1.
AC代码
特意用逆序来做的下降序列, 写的有一点丑, 不想细改了. 代码应该是没问题的.
1 | // 数组a[] 存储原数据, b[] 存储a 的逆序, 用两个函数分别求LIS. |
最长公共子序列
大致算法
记串 \(a\) 和串 \(b\) 的以 \(i\) 和 \(j\) 结尾的前缀分别为 \(A_i\) 和 \(B_j\), 令 \(dp[i, j]\) 表示 \(A_i\) 与 \(B_j\) 的LCS长度, 则有:
\[dp[i,j] = \begin{cases} 0 & i = 0~\text{or}~ j=0 \\ dp[i-1,j-1]+1 & i, j>0,~a_i=b_j \\ \max\{dp[i-1, j], dp[i, j-1]\} & i, j>0,~a_i\neq b_j \end{cases}\]
实现代码
1 | // 注意下标, 从1 开始, 输入时也要注意. |
POJ 1458: Common Subsequence
Description
A subsequence of a given sequence is the given sequence with some elements (possible none) left out. Given a sequence X = < x1, x2, …, xm > another sequence Z = < z1, z2, …, zk > is a subsequence of X if there exists a strictly increasing sequence < i1, i2, …, ik > of indices of X such that for all j = 1,2,…,k, xij = zj. For example, Z = < a, b, f, c > is a subsequence of X = < a, b, c, f, b, c > with index sequence < 1, 2, 4, 6 >. Given two sequences X and Y the problem is to find the length of the maximum-length common subsequence of X and Y.
Input
The program input is from the std input. Each data set in the input contains two strings representing the given sequences. The sequences are separated by any number of white spaces. The input data are correct.
Output
For each set of data the program prints on the standard output the length of the maximum-length common subsequence from the beginning of a separate line.
Sample Input
abcfbc abfcab
programming contest
abcd mnp
Sample Output
4
2
0
AC代码
一定要注意输入和下标!!! 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
using namespace std;
const int maxn = 1005;
int dp[maxn][maxn];
char a[maxn], b[maxn];
void init(int n, int m)
{
memset(dp, 0, sizeof(dp)); // 应该没必要全都初始化
for(int i = 1; i <= n; i++)
for(int j = 1; j <= m; j++)
if(a[i] == b[j]) dp[i][j] = dp[i - 1][j - 1] + 1;
else dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
}
int main()
{
while(scanf("%s%s", a + 1, b + 1) != EOF)
{
int n = strlen(a + 1);
int m = strlen(b + 1);
init(n, m);
printf("%d\n", dp[n][m]);
}
return 0;
}
最大子段和与最大子矩阵
最大子段和
最大子段和问题：求解给定数组 \(a\) 的所有子段中, 和最大的一个.
根据问题, 显然有如下的暴力方法:
1
2
3
4
5// 给定原数组int a[], 元素个数 n.
int ans = a[0];
for(int i = 0; i < n; i++)
for(int j = i; j < n; j++)
ans = max(ans, SUM(a[i]...a[j]));
考虑上求和的 \(O(n)\), 该算法的复杂度为 \(O(n^3)\). 如果优化掉求和的 \(O(n)\), 可优化为 \(O(n^2)\), 具体优化不在此赘述, 毕竟优化完了也很慢…
如使用 \(dp[i]\) 表示以第 \(i\) 位结尾的最大子段和, 则可以使问题得到极大的简化: \[dp[i]=\max(dp[i - 1] + a[i], a[i]),\] \[ans = \max\limits_{0\leqslant i\leqslant n-1}(dp[i]).\] 根据该递推式很容易就可以写出如下代码: 1
2
3
4
5
6
7
8
9
10
11
12// 给定原数组int a[], 元素个数 n. 下标从0 开始.
// 中间变量int dp[], dp[i]表示以第i 位结尾的最大子段和
int solve(int n)
{
dp[0] = a[0];
for(int i = 1; i < n; i++)
dp[i] = max(dp[i - 1] + a[i], a[i]);
int res = a[0];
for(int i = 0; i < n; i++)
res = max(res, b[i]);
return res
}
容易得出该算法的复杂度为 \(O(n)\). 是最快的求解算法.
同时不难想到, 最大子段和还有递归的求解方法, 时间复杂度为 \(O(n\log n)\), 不再赘述.
最大子矩阵
最大子段和的求解方式可直接应用于求解最大子矩阵问题:
- 先将矩阵的行求和压缩: 对每行的第 \(i\) 到第 \(j\) 求和.
- 再对压缩后的 \(sum\) 数组做最大子段和.
- 变换 \(i\), \(j\), 取最大值.
求和数组 \(sum\) 的转移方式也就是上文中暴力求最大子段和中求和时间的优化, 其实相当简单: 1
2
3
4
5
6
7
8
9
10// 给定原矩阵int a[][maxn], 行数m, 列数n. a[i][j] 表示第i 行第j 个, 下标从0 开始.
// 列和数组int sum[], sum[r] 表示第r 行的状态.
for(int i = 0; i < n; i++) // 枚举起点
{
for(int r = 0; r < m; r++) // 初始化
sum[r] = a[r][i];
for(int j = i + 1; j < n; j++) // 枚举终点
for(int r = 0; r < m; r++) // 更新每一行的和
sum[r] += a[r][j];
}
显然我们只需要对每次处理好的 \(sum\) 数组做最大子段和, 然后取最大值. 时间复杂度应为 \(O(n^3)\).
代码如下: 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
26int solve(int m, int n)
{
int res = a[0][0];
for(int i = 0; i < n; i++)
{
for(int r = 0; r < n; r++)
sum[r] = a[r][i];
dp[0] = sum[0];
for(int r = 1; r < m; r++)
dp[r] = max(dp[r - 1] + sum[r], sum[r]);
for(int r = 0; r < m; r++)
res = max(res, dp[r]);
for(int j = i + 1; j < n; j++)
{
for(int r = 0; r < m; r++)
sum[r] += a[r][j];
dp[0] = sum[0];
for(int r = 1; r < m; r++)
dp[i] = max(dp[i - 1] + sum[i], sum[i]);
for(int r = 0; r < m; r++)
res = max(res, dp[r]);
}
}
return res;
}
把最大子段和的函数封装一下可能会更好看, 我懒的搞…
百练 2766: 最大子矩阵
总时间限制: 1000ms 内存限制: 65536kB
描述
已知矩阵的大小定义为矩阵中所有元素的和。给定一个矩阵，你的任务是找到最大的非空(大小至少是1 * 1)子矩阵。
比如，如下4 * 4的矩阵
\[\begin{bmatrix} 0 & -2 & -7 & 0 \\ 9 & 2 & -6 & 2 \\ -4 & 1 & -4 & 1 \\ -1 & 8 & 0 & -2 \end{bmatrix}\]
的最大子矩阵是
\[\begin{bmatrix} 9 & 2 \\ -4 & 1 \\ -1 & 8 \end{bmatrix}\]
这个子矩阵的大小是15。
输入
输入是一个N * N的矩阵。输入的第一行给出N (0 < N <= 100)。再后面的若干行中，依次（首先从左到右给出第一行的N个整数，再从左到右给出第二行的N个整数……）给出矩阵中的N2个整数，整数之间由空白字符分隔（空格或者空行）。已知矩阵中整数的范围都在[-127, 127]。
输出
输出最大子矩阵的大小。
样例输入
4
0 -2 -7 0 9 2 -6 2
-4 1 -4 1 -1
8 0 -2
样例输出
15
思路
有啥好说的么…很裸. 这题机试要是过不去的话我觉得我可以去死了..
AC代码
懒, 用了 cin, cout. 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
47
using namespace std;
const int maxn = 105;
int a[maxn][maxn], dp[maxn], sum[maxn];
int solve(int m, int n)
{
int res = a[0][0];
for (int i = 0; i < n; i++)
{
for (int r = 0; r < m; r++)
sum[r] = a[r][i];
dp[0] = sum[0];
for (int r = 1; r < m; r++)
dp[r] = max(dp[r - 1] + sum[r], sum[r]);
for (int r = 0; r < m; r++)
res = max(res, dp[r]);
for (int j = i + 1; j < n; j++)
{
for (int r = 0; r < m; r++)
sum[r] += a[r][j];
dp[0] = sum[0];
for (int r = 1; r < m; r++)
dp[r] = max(dp[r - 1] + sum[r], sum[r]);
for (int r = 0; r < m; r++)
res = max(res, dp[r]);
}
}
return res;
}
int main()
{
int n;
while (cin >> n)
{
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
cin >> a[i][j];
cout << solve(n, n) << endl;
}
return 0;
}
背包相关问题
背包相关的问题的背景大都是往容量有限的背包中装一些给定的物品, 使得总价值尽可能大. 感觉机试中比较多的就是0-1背包.
0-1背包
有 \(n\) 件物品和一个容量为 \(V\) 的背包. 放入第 \(i\) 件物品耗费的费用是 \(c_i\), 得到的 价值是 \(w_i\). 求解将哪些物品装入背包可使价值总和最大.
实现代码如下:
1 | // maxc 表示cost 最大值, maxn 表示n 最大值. |
百练 3714: 点菜问题
题目链接: http://bailian.openjudge.cn/practice/3714/
总时间限制: 1000ms 内存限制: 65536kB
描述
北大网络实验室经常有活动需要叫外买，但是每次叫外买的报销经费的总额最大为C元，有N种菜可以点 ，经过长时间的点菜，网络实验室对于每种菜i都有一个量化的评价分数（表示这个菜可口程度），为Vi，每种菜的价格为Pi, 问如何选择各种菜，使得在报销额度范围内能使点到的菜的总评价分数最大？ 注意：由于需要营养多样化，每种菜只能点一次。
输入
输入的第一行有两个整数C（1 <= C <= 1000）和N（1 <= N <= 100），C代表总共能够报销的额度，N>代表能点菜的数目。接下来的N行每行包括两个在1到100之间（包括1和100）的的整数，分别表示菜的>价格和菜的评价分数。
输出
输出只包括一行，这一行只包含一个整数，表示在报销额度范围内，所点的菜得到的最大评价分数。
样例输入
90 4
20 25
30 20
40 50
10 18
40 2
25 30
10 8
样例输出
95
38
AC代码
1 |
|
百练 2773: 采药
总时间限制: 1000ms 内存限制: 65536kB
描述
辰辰是个很有潜能、天资聪颖的孩子，他的梦想是称为世界上最伟大的医师。为此，他想拜附近最有威望的医师为师。医师为了判断他的资质，给他出了一个难题。医师把他带到个到处都是草药的山洞里对他说：“孩子，这个山洞里有一些不同的草药，采每一株都需要一些时间，每一株也有它自身的价值。我会给你一段时间，在这段时间里，你可以采到一些草药。如果你是一个聪明的孩子，你应该可以让采到的草药的总价值最大。”
如果你是辰辰，你能完成这个任务吗？
输入
输入的第一行有两个整数T（1 <= T <= 1000）和M（1 <= M <= 100），T代表总共能够用来采药的时间，M代表山洞里的草药的数目。接下来的M行每行包括两个在1到100之间（包括1和100）的的整数，分别表示采摘某株草药的时间和这株草药的价值。
输出
输出只包括一行，这一行只包含一个整数，表示在规定的时间内，可以采到的草药的最大总价值。
样例输入
70 3
71 100
69 1
1 2
样例输出
3
AC代码
1 |
|
合并石子/矩阵链乘
algorithm.openjudge 合并石子
描述
在一个操场上一排地摆放着Ｎ堆石子。现要将石子有次序地合并成一堆。规定每次只能选相邻的２堆石子合并成新的一堆，并将新的一堆石子数记为该次合并的得分。 试设计一个程序，计算出将Ｎ堆石子合并成一堆的最小得分。
输入
第一行为一个正整数\(N\) \((2\leqslant N\leqslant 100)\)； 以下Ｎ行,每行一个正整数，小于$10000，分别表示第 \(i\) 堆石子的个数 \((1≤i≤N)\)。 #### 输出 为一个正整数，即最小得分。 #### 样例输入 7 13 7 8 16 21 4 18 #### 样例输出 239
最大上升子序列和
牛客网: 最大上升子序列和
题目链接: https://www.nowcoder.com/practice/dcb97b18715141599b64dbdb8cdea3bd?tpId=40&tqId=21409&tPage=4&rp=4&ru=/ta/kaoyan&qru=/ta/kaoyan/question-ranking
题目描述
一个数的序列bi，当b1 < b2 < … < bS的时候，我们称这个序列是上升的。对于给定的一个序列(a1, a2, …,aN)，我们可以得到一些上升的子序列(ai1, ai2, …, aiK)，这里1 <= i1 < i2 < … < iK <= N。比如，对于序列(1, 7, 3, 5, 9, 4, 8)，有它的一些上升子序列，如(1, 7), (3, 4, 8)等等。这些子序列中序列和最大为18，为子序列(1, 3, 5, 9)的和. 你的任务，就是对于给定的序列，求出最大上升子序列和。注意，最长的上升子序列的和不一定是最大的，比如序列(100, 1, 2, 3)的最大上升子序列和为100，而最长上升子序列为(1, 2, 3)。
输入描述
输入包含多组测试数据。 每组测试数据由两行组成。第一行是序列的长度N (1 <= N <= 1000)。第二行给出序列中的N个整数，这些整数的取值范围都在0到10000（可能重复）。
输出描述
对于每组测试数据，输出其最大上升子序列和。
样例输入
7
1 7 3 5 9 4 8
样例输出
18
大致思路
仍然是经典的子段/子序列dp的思路, 设原数组为 \(a\), 记 \(dp[i]\) 为以第 \(i\) 位结尾的最大上升子序列和, 则考虑 \(i<j\), 若 \(a[j] < a[i]\), 则 \(a[i]\) 接在以 \(a[j]\) 结尾的最大和子序列后可以构成一个以 \(a[i]\) 结尾的子序列, 可用该子序列的和去更新 \(dp[i]\) 的值, 即: \[dp[i] = \max \left( \max_{0<j<i\atop a[j]<a[i]} ( dp[j]+a[i] ), a[i] \right).\]
AC代码
1 |
|
组合数的递推
这是一个很蠢的东西, 勉强算作动态规划吧.. 但实际只应算作递推.
原理
根本不用细说…就这一个式子, 叫做pascal公式. \[\binom{n}{k}=\binom{n-1}{k}+\binom{n-1}{k-1}.\]
实现代码
1 | // c[n][k] 表示n 中取k. |