算法学习
题单传送门
求最长上升序列（线性dp模板）
Description
设有由 \(n\) 个不相同的整数组成的数列，记为:\(b_1\)、\(b_2\)、\(……\)、\(b_n\) 且 \(b_i<>b_j (i<>j)\)，若存在\(i_1<i_2<i_3< … < i_e\) 且有 \(b_{i1}<b_{i2}< … <b_{ie}\) 则称为长度为 \(e\) 的不下降序列。
程序要求，当原数列出之后，求出最长的上升序列。
例如 \(13\)，\(7\)，\(9\)，\(16\)，\(38\)，\(24\)，\(37\)，\(18\)，\(44\)，\(19\)，\(21\)，\(22\)，\(63\)，\(15\)。例中 \(13\)，\(16\)，\(18\)，\(19\)，\(21\)，\(22\)，\(63\) 就是一个长度为 \(7\) 的不下降序列，同时也有 \(7\)，\(9\)，\(16\)，\(18\)，\(19\)，\(21\)，\(22\)，\(63\) 长度为 \(8\) 的不下降序列。
Input Format
只有一行，为若干正整数（最多 \(1000\) 个数）
Output Format
为两行，第一行为最上升序列的长度。 第二行为该序列
Sample
样例输入
13 7 9 16 38 24 37 18 44 19 21 22 63 15
样例输出
max=8
7 9 16 18 19 21 22 63
思路
模板线性dp，但是折磨了我肥肠久。
die 码
#include <bits/stdc++.h>
using namespace std;
const int N = 1010;
int a[N], f[N], p[N];
int res = 1, n;
void out(int k) {
if (p[k] != 0)
out(p[k]);
cout << a[k] << " ";
}
int main() {
while (cin >> a[++n]);
for (int i = 1; i <= n; i++) {
f[i] = 1;
for (int j = 1; j < i; j++) {
if (a[j] < a[i]) {
if (f[j] + 1 > f[i]) {
f[i] = f[j] + 1;
p[i] = j;
}
res = max(res, f[i]);
}
}
}
cout << "max=" << res << endl;
int k = 1;
while (f[k] != res)
k++;
out(k);
return 0;
}
备注
附洛谷题面，和上文代码略有差异。
合唱队列
Description
\(N\) 位同学站成一排，音乐老师要请其中的 \((N-K)\) 位同学出列，使得剩下的 \(K\) 位同学排成合唱队形。合唱队形是指这样的一种队形：设 \(K\) 位同学从左到右依次编号为 \(1, 2, …, K\)，他们的身高分别为 \(T_1, T_2, …, T_K\)，则他们的身高满足 $T_1 < T_2 < … < T_i \(，\)T_i > T_{i+1} > … > T_K (1\le i\le K)$。
你的任务是，已知所有 \(N\) 位同学的身高，计算最少需要几位同学出列，可以使得剩下的同学排成合唱队形。
Input Format
输入文件 \(chorus.in\) 的第一行是一个整数 \(N(2\le N\le 100)\)，表示同学的总数。第二行有 \(n\) 个整数，用空格分隔，第 \(i\) 个整数 \(T_i(130\le Ti\le 230)\) 是第 \(i\) 位同学的身高（厘米）。
对于 \(50\%\) 的数据，保证有 \(n\le 20\)；对于全部的数据，保证有 \(n\le 100\)。
Output Format
输出文件 \(chorus.out\) 包括一行，这一行只包含一个整数，就是最少需要几位同学出列。
Sample
样例输入
8
186 186 150 200 160 130 197 220
样例输出
4
思路
和模板基本相同，跑两次 \(dp\) 即可。
die码
#include <bits/stdc++.h>
using namespace std;
int n, res;
int a[105], dp1[105], dp2[105];
int main() {
cin >> n;
for (int i = 1; i <= n; i++)
cin >> a[i];
memset(dp1, 0, sizeof(dp1));
memset(dp2, 0, sizeof(dp2));
for (int i = 1; i <= n; i++) {
dp1[i] = 1;
for (int j = 1; j < i; j++)
if (a[i] > a[j] && dp1[j] + 1 > dp1[i])
dp1[i] = dp1[j] + 1;
}
for (int i = n; i >= 1; i--) {
dp2[i] = 1;
for (int j = i; j <= n; j++) {
if (a[i] > a[j] && dp2[j] + 1 > dp2[i])
dp2[i] = dp2[j] + 1;
}
}
for (int i = 1; i <= n; i++)
if (dp1[i] + dp2[i] > res)
res = dp1[i] + dp2[i];
res = n - res + 1;
cout << res;
return 0;
}
备注
附洛谷题面，与上文代码相同。
导弹拦截简单版
Description
某国为了防御敌国的导弹袭击，发展出一种导弹拦截系统。但是这种导弹拦截系统有一个缺陷：虽然它的第一发炮弹能够到达任意的高度，但是以后每一发炮弹都不能高于前一发的高度。某天，雷达捕捉到敌国的导弹来袭。由于该系统还在试用阶段，所以只有一套系统，因此有可能不能拦截所有的导弹。
输入导弹依次飞来的高度（雷达给出的高度数据是不大于 \(30000\) 的正整数，导弹数不超过 \(1000\)），计算这套系统最多能拦截多少导弹，如果要拦截所有导弹最少要配备多少套这种导弹拦截系统。
Input Format
输入只有一行，为若干个正整数，一次为导弹的高度。
Output Format
第一行为最多能拦截的导弹数；
第二行为要拦截所有导弹最少要配备的系统数
Sample
样例输入
389 207 155 300 299 170 158 65
样例输出
6
2
思路
同样是简单的 \(dp\) 题，当 \(a_j\) 的值大于 \(a_i\) 时，即应换另一套系统时对 \(do2\) 进行状态转移，否则是 \(dp1\)。
die码
#include <bits/stdc++.h>
using namespace std;
int a[1005], dp1[1005], dp2[1005];
int n, res, minn;
int main() {
while (cin >> a[++n]);
for (int i = 1; i < n; i++) {
dp1[i] = 1;
dp2[i] = 1;
for (int j = 1; j < i; j++) {
if (a[i] <= a[j])
dp1[i] = max(dp1[i], dp1[j] + 1);
else
dp2[i] = max(dp2[i], dp2[j] + 1);
}
res = max(res, dp1[i]);
minn = max(minn, dp2[i]);
}
cout << res << endl << minn;
return 0;
}
备注
附洛谷题面，与上文代码略有差异。