|
|
## $LIS$+$LCS$专题
|
|
|
|
|
|
#### 一、基础题
|
|
|
**[$AcWing$ $895$. 最长上升子序列](https://www.acwing.com/problem/content/897/)**
|
|
|
|
|
|
**时间复杂度**
|
|
|
$O(N^2)$
|
|
|
|
|
|
**状态表示**
|
|
|
$f[i]$:以$a[i]$结尾的最长上升子序列长度
|
|
|
|
|
|
**状态转移**
|
|
|
$f[i] = max(f[i], f[j] + 1)(a[i] > a[j])$
|
|
|
|
|
|
**初始值**
|
|
|
$f[i] = 1$
|
|
|
> **解释**：一个以$i$结尾的序列，最少可以是$i$自己，长度是$1$
|
|
|
|
|
|
**代码**
|
|
|
```cpp {.line-numbers}
|
|
|
#include <bits/stdc++.h>
|
|
|
|
|
|
using namespace std;
|
|
|
const int N = 1010;
|
|
|
|
|
|
int n;
|
|
|
int a[N], f[N];
|
|
|
int res;
|
|
|
|
|
|
int main() {
|
|
|
cin >> n;
|
|
|
for (int i = 1; i <= n; i++) cin >> a[i];
|
|
|
|
|
|
for (int i = 1; i <= n; i++) {
|
|
|
f[i] = 1; // 一个以i结尾的序列，最少可以是i自己，长度是1
|
|
|
for (int j = 1; j < i; j++)
|
|
|
if (a[i] > a[j]) // i可以接在j后面
|
|
|
f[i] = max(f[i], f[j] + 1); // 借力于j
|
|
|
res = max(res, f[i]);
|
|
|
}
|
|
|
printf("%d", res);
|
|
|
return 0;
|
|
|
}
|
|
|
|
|
|
```
|
|
|
|
|
|
|
|
|
**[$AcWing$ $896$. 最长上升子序列 II ](https://www.acwing.com/problem/content/898/)**
|
|
|
|
|
|
数据量增大:$N<=100000$
|
|
|
|
|
|
**思想**
|
|
|
对于同样长度的子串，希望它的末端越小越好，这样后面更易扩展它,使数列更长。
|
|
|
|
|
|
**时间复杂度**
|
|
|
$O(LogN*N)$
|
|
|
|
|
|
**状态表示**
|
|
|
$f[i]$表示 **长度为$i$** 的递增子序列中，**末尾元素最小** 的是$f[i]$
|
|
|
|
|
|
**答案**
|
|
|
$fl$
|
|
|
|
|
|
**特点与总结**
|
|
|
① $f[]$数组是一个单调上升的数组,这是二分的基础
|
|
|
② 每个长度都争取替换掉前面记录数组中第一个大于等于自己的数字，以保证长度不变的情况下，数字最小。
|
|
|
|
|
|
**学习方法**
|
|
|
举栗子
|
|
|
|
|
|
**代码**
|
|
|
```cpp {.line-numbers}
|
|
|
#include <bits/stdc++.h>
|
|
|
|
|
|
using namespace std;
|
|
|
const int N = 100010;
|
|
|
|
|
|
int n, a[N];
|
|
|
|
|
|
// 数组模拟
|
|
|
int f[N], fl;
|
|
|
|
|
|
int main() {
|
|
|
cin >> n;
|
|
|
for (int i = 0; i < n; i++) cin >> a[i];
|
|
|
|
|
|
// 1、首个元素
|
|
|
f[0] = a[0];
|
|
|
|
|
|
// 2、后续元素开始计算
|
|
|
for (int i = 1; i < n; i++) {
|
|
|
if (a[i] > f[fl])
|
|
|
f[++fl] = a[i];
|
|
|
else
|
|
|
// 利用STL的二分，在f中查找第一个大于等于a[i]的值，并完成替换
|
|
|
*lower_bound(f, f + fl, a[i]) = a[i];
|
|
|
}
|
|
|
// 栈内元素数量就是答案
|
|
|
printf("%d\n", fl + 1);
|
|
|
return 0;
|
|
|
}
|
|
|
|
|
|
```
|
|
|
|
|
|
|
|
|
**[$AcWing$ $897$. 最长公共子序列](https://www.acwing.com/problem/content/899/)**
|
|
|
|
|
|
**状态表示**
|
|
|
$f[i][j]$:$a[]$以$i$结尾，$b[]$以$j$结尾的 **最长公共子序列长度**
|
|
|
> **说明**：没有说$a[i]$或者$b[j]$一定要出现在最长公共子序列当中！这个最长公共子序列，可能是$a[]$和$b[]$的一些前序组成的，$a[i],b[j]$也可能没有对结果产生贡献。
|
|
|
|
|
|
* 当$a[i]==b[j]$时，看一下两个字符串的前序，发现在少了$a[i],b[j]$后，转化为子问题$f[i-1][j-1]$,问题转化为$$f[i][j]=f[i-1][j-1]+1$$
|
|
|
|
|
|
* 当$a[i] \neq b[j]$时：
|
|
|
* 如果$a[i]$不产生贡献，那么把它干掉$f[i-1][j]$
|
|
|
* 如果$b[j]$不产生贡献，那么把它干掉$f[i][j-1]$3
|
|
|
|
|
|
**答案**
|
|
|
$f[n][m]$
|
|
|
|
|
|
**代码**
|
|
|
```cpp {.line-numbers}
|
|
|
#include <bits/stdc++.h>
|
|
|
|
|
|
using namespace std;
|
|
|
const int N = 1010;
|
|
|
int n, m;
|
|
|
char a[N], b[N];
|
|
|
int f[N][N];
|
|
|
|
|
|
int main() {
|
|
|
// 递推式出现f[i-1][j-1]，如果i,j从0开始会出现负值，所以下标从1开始
|
|
|
cin >> n >> m >> a + 1 >> b + 1;
|
|
|
for (int i = 1; i <= n; i++)
|
|
|
for (int j = 1; j <= m; j++) {
|
|
|
if (a[i] == b[j])
|
|
|
f[i][j] = f[i - 1][j - 1] + 1;
|
|
|
else
|
|
|
f[i][j] = max(f[i - 1][j], f[i][j - 1]);
|
|
|
}
|
|
|
printf("%d", f[n][m]);
|
|
|
return 0;
|
|
|
}
|
|
|
```
|
|
|
|
|
|
#### 二、进阶题
|
|
|
**[$AcWing$ $1017$. 怪盗基德的滑翔翼](https://www.acwing.com/problem/content/1019/)**
|
|
|
|
|
|
朴素$O(N^2)$版本
|
|
|
```cpp {.line-numbers}
|
|
|
#include <bits/stdc++.h>
|
|
|
|
|
|
using namespace std;
|
|
|
|
|
|
const int N = 110;
|
|
|
int n; // 楼房的个数
|
|
|
int w[N]; // 楼房的高度数组
|
|
|
int f[N]; // LIS结果数组，DP结果
|
|
|
|
|
|
int main() {
|
|
|
int T;
|
|
|
cin >> T;
|
|
|
while (T--) {
|
|
|
// 保持好习惯，多组测试数据，记得每次清空结果数组
|
|
|
memset(f, 0, sizeof f);
|
|
|
int res = 0;
|
|
|
|
|
|
cin >> n;
|
|
|
for (int i = 1; i <= n; i++) cin >> w[i];
|
|
|
|
|
|
// 从左到右,求一遍最长上升子序列[朴素O(N^2)版本]
|
|
|
for (int i = 1; i <= n; i++) {
|
|
|
f[i] = 1;
|
|
|
for (int j = 1; j < i; j++)
|
|
|
if (w[i] > w[j]) f[i] = max(f[i], f[j] + 1);
|
|
|
res = max(res, f[i]);
|
|
|
}
|
|
|
|
|
|
// 反向求解 LIS问题
|
|
|
for (int i = n; i >= 1; i--) {
|
|
|
f[i] = 1;
|
|
|
for (int j = n; j > i; j--)
|
|
|
if (w[i] > w[j]) f[i] = max(f[i], f[j] + 1);
|
|
|
res = max(res, f[i]);
|
|
|
}
|
|
|
|
|
|
printf("%d\n", res);
|
|
|
}
|
|
|
return 0;
|
|
|
}
|
|
|
```
|
|
|
优化$O(LogN*N)$版本
|
|
|
```cpp {.line-numbers}
|
|
|
#include <bits/stdc++.h>
|
|
|
|
|
|
using namespace std;
|
|
|
|
|
|
const int N = 110;
|
|
|
int n; // 楼房的个数
|
|
|
int a[N]; // 楼房的高度数组
|
|
|
|
|
|
// 数组模拟栈
|
|
|
int f[N], fl;
|
|
|
int g[N], gl;
|
|
|
int res;
|
|
|
|
|
|
int main() {
|
|
|
int T;
|
|
|
cin >> T;
|
|
|
while (T--) {
|
|
|
// 保持好习惯，多组测试数据，记得每次清空结果数组
|
|
|
memset(f, 0, sizeof f);
|
|
|
memset(g, 0, sizeof g);
|
|
|
fl = 0, gl = 0;
|
|
|
|
|
|
cin >> n;
|
|
|
for (int i = 1; i <= n; i++) cin >> a[i];
|
|
|
|
|
|
// 正着求
|
|
|
for (int i = 1; i <= n; i++) {
|
|
|
if (a[i] > f[fl])
|
|
|
f[++fl] = a[i];
|
|
|
else
|
|
|
*lower_bound(f + 1, f + 1 + fl, a[i]) = a[i];
|
|
|
}
|
|
|
|
|
|
// 反着求
|
|
|
for (int i = n; i; i--) {
|
|
|
if (a[i] > g[gl])
|
|
|
g[++gl] = a[i];
|
|
|
else
|
|
|
*lower_bound(g + 1, g + 1 + gl, a[i]) = a[i];
|
|
|
}
|
|
|
// pk的最大结果
|
|
|
res = max(fl, gl);
|
|
|
// 输出
|
|
|
printf("%d\n", res);
|
|
|
}
|
|
|
return 0;
|
|
|
}
|
|
|
```
|
|
|
|
|
|
**[$AcWing$ $1014$. 登山](https://www.acwing.com/problem/content/1016/)**
|
|
|
```cpp {.line-numbers}
|
|
|
#include <bits/stdc++.h>
|
|
|
|
|
|
using namespace std;
|
|
|
|
|
|
const int N = 1010;
|
|
|
int n; // 山的个数
|
|
|
int a[N]; // 山的高度数组
|
|
|
int f[N]; // 最长上升子序列
|
|
|
int g[N]; // 最长下降子序列
|
|
|
int res;
|
|
|
|
|
|
int main() {
|
|
|
cin >> n;
|
|
|
for (int i = 1; i <= n; i++) cin >> a[i];
|
|
|
|
|
|
// 正向
|
|
|
for (int i = 1; i <= n; i++) {
|
|
|
f[i] = 1;
|
|
|
for (int j = 1; j < i; j++)
|
|
|
if (a[i] > a[j]) f[i] = max(f[i], f[j] + 1);
|
|
|
}
|
|
|
// 反向
|
|
|
for (int i = n; i >= 1; i--) {
|
|
|
g[i] = 1;
|
|
|
for (int j = n; j > i; j--)
|
|
|
if (a[i] > a[j]) g[i] = max(g[i], g[j] + 1);
|
|
|
}
|
|
|
|
|
|
// 每个点，都可能是两者相加的最大位置处，所以，需要枚举每个点，每个点都有资格参评最优点
|
|
|
// 因为最终的那个中间点，左边计算了一次，右边又计算了一次，需要减1去重复
|
|
|
for (int i = 1; i <= n; i++) res = max(res, f[i] + g[i] - 1);
|
|
|
// 输出
|
|
|
printf("%d\n", res);
|
|
|
return 0;
|
|
|
}
|
|
|
```
|
|
|
|
|
|
**[$AcWing$ $482$. 合唱队形](https://www.acwing.com/problem/content/484/)**
|
|
|
```cpp {.line-numbers}
|
|
|
#include <bits/stdc++.h>
|
|
|
|
|
|
using namespace std;
|
|
|
const int N = 1010;
|
|
|
int n, a[N];
|
|
|
int f[N], fl, p1[N];
|
|
|
int g[N], gl, p2[N];
|
|
|
|
|
|
int res;
|
|
|
|
|
|
int main() {
|
|
|
cin >> n;
|
|
|
for (int i = 1; i <= n; i++) cin >> a[i];
|
|
|
|
|
|
// 正向
|
|
|
f[++fl] = a[1];
|
|
|
p1[1] = 1;
|
|
|
|
|
|
for (int i = 2; i <= n; i++)
|
|
|
if (a[i] > f[fl]) {
|
|
|
f[++fl] = a[i];
|
|
|
p1[i] = fl;
|
|
|
} else {
|
|
|
int t = lower_bound(f + 1, f + fl + 1, a[i]) - f;
|
|
|
f[t] = a[i];
|
|
|
p1[i] = t;
|
|
|
}
|
|
|
|
|
|
// 反向
|
|
|
g[++gl] = a[n];
|
|
|
p2[n] = 1;
|
|
|
|
|
|
for (int i = n - 1; i >= 1; i--)
|
|
|
if (a[i] > g[gl]) {
|
|
|
g[++gl] = a[i];
|
|
|
p2[i] = gl;
|
|
|
} else {
|
|
|
int t = lower_bound(g + 1, g + gl + 1, a[i]) - g;
|
|
|
g[t] = a[i];
|
|
|
p2[i] = t;
|
|
|
}
|
|
|
|
|
|
for (int i = 1; i <= n; i++) res = max(res, p2[i] + p1[i] - 1);
|
|
|
|
|
|
printf("%d\n", n - res);
|
|
|
return 0;
|
|
|
}
|
|
|
```
|
|
|
**[$AcWing$ $1012$. 友好城市](https://www.acwing.com/problem/content/1014/)**
|
|
|
① 数对
|
|
|
② 左端点排序
|
|
|
③ 对于右端点组成的数组，求最长上升子序列长度
|
|
|
```cpp {.line-numbers}
|
|
|
#include <bits/stdc++.h>
|
|
|
|
|
|
using namespace std;
|
|
|
typedef pair<int, int> PII;
|
|
|
#define x first
|
|
|
#define y second
|
|
|
const int N = 5010;
|
|
|
PII a[N]; // 南岸和北岸的一对友好城市的坐标
|
|
|
int f[N]; // 记录以f[i]为结尾的一对友好城市时的，不产生交叉的最多城市对数
|
|
|
int n; // n组友好城市
|
|
|
int res;
|
|
|
|
|
|
int main() {
|
|
|
cin >> n;
|
|
|
for (int i = 1; i <= n; i++) cin >> a[i].x >> a[i].y;
|
|
|
sort(a + 1, a + 1 + n); // PII默认按第一维度first进行排序
|
|
|
|
|
|
// LIS
|
|
|
for (int i = 1; i <= n; i++) {
|
|
|
f[i] = 1;
|
|
|
for (int j = 1; j < i; j++)
|
|
|
if (a[i].y > a[j].y)
|
|
|
f[i] = max(f[i], f[j] + 1);
|
|
|
res = max(res, f[i]);
|
|
|
}
|
|
|
printf("%d\n", res);
|
|
|
return 0;
|
|
|
}
|
|
|
```
|
|
|
|
|
|
```cpp {.line-numbers}
|
|
|
#include <bits/stdc++.h>
|
|
|
|
|
|
using namespace std;
|
|
|
typedef pair<int, int> PII;
|
|
|
#define x first
|
|
|
#define y second
|
|
|
|
|
|
const int N = 5010;
|
|
|
PII a[N]; // 南岸和北岸的一对友好城市的坐标
|
|
|
int f[N], fl; // 数组模拟栈
|
|
|
int n; // n组友好城市
|
|
|
int res;
|
|
|
|
|
|
int main() {
|
|
|
cin >> n;
|
|
|
for (int i = 1; i <= n; i++) cin >> a[i].x >> a[i].y;
|
|
|
sort(a + 1, a + 1 + n);
|
|
|
|
|
|
f[++fl] = a[1].y;
|
|
|
for (int i = 2; i <= n; i++) {
|
|
|
if (a[i].y > f[fl])
|
|
|
f[++fl] = a[i].y;
|
|
|
else
|
|
|
*lower_bound(f + 1, f + 1 + fl, a[i].y) = a[i].y;
|
|
|
}
|
|
|
|
|
|
printf("%d\n", fl);
|
|
|
return 0;
|
|
|
}
|
|
|
```
|
|
|
|
|
|
**[$AcWing$ $1016$. 最大上升子序列和](https://www.acwing.com/problem/content/1012/)**
|
|
|
|
|
|
```cpp {.line-numbers}
|
|
|
#include <bits/stdc++.h>
|
|
|
using namespace std;
|
|
|
|
|
|
// 最大上升子序列和
|
|
|
int n;
|
|
|
const int N = 100010;
|
|
|
int a[N];
|
|
|
int f[N];//以第i个元素结尾的最大子序列和
|
|
|
int res;
|
|
|
|
|
|
int main() {
|
|
|
cin >> n;
|
|
|
for (int i = 1; i <= n; i++) cin >> a[i];
|
|
|
|
|
|
for (int i = 1; i <= n; i++) {
|
|
|
f[i] = a[i]; // 最大上升子序列（个数）这里是1,此处是a[i]
|
|
|
for (int j = 1; j < i; j++)
|
|
|
// 最大上升子序列（个数）这里是加1,此处是+a[i]
|
|
|
if (a[i] > a[j]) f[i] = max(f[i], f[j] + a[i]);
|
|
|
res = max(res, f[i]);
|
|
|
}
|
|
|
printf("%d ", res);
|
|
|
return 0;
|
|
|
}
|
|
|
```
|
|
|
**魔改 最长上升子序列和**
|
|
|
|
|
|
**[$AcWing$ $1010$. 拦截导弹](https://www.acwing.com/problem/content/1012/)**
|
|
|
|
|
|
> **题目要求**：但是这种导弹拦截系统有一个缺陷：虽然它的第一发炮弹能够到达任意的高度，但是以后每一发炮弹都不能高于前一发的高度。
|
|
|
|
|
|
**数组含义**
|
|
|
$q[],ql$:已经创建了$ql$套导弹系统,$q[i]$中记录的是第$i$套导弹系统的最大拦截高度
|
|
|
|
|
|
**举栗子,总结规律**
|
|
|
$q[0]:5$
|
|
|
$q[1]:6$
|
|
|
> **举的这个栗子对吗？**
|
|
|
> 我们思考一下：原来有一套导弹拦截系统，上次的高度是$5$,现在第二颗导弹的高度是$6$，根据题目要求，它不能高于前一发的高度，所以只能再开一个导弹拦截系统，所以，第二个是$6$是正确的。
|
|
|
|
|
|
现在来了一个高度=$4$,根据上面的原则，可以接在$5$后面，也可以接在$6$后面，我们为了不浪费$6$,就选择了接在$5$后面，放到$q[0]$里，修改$q[0]=4$
|
|
|
$q[0]:4$
|
|
|
$q[1]:6$
|
|
|
原来的数组是单调上升的，修改后值也是在上下夹着中间的，也依然是单调上升的。
|
|
|
|
|
|
再比如：
|
|
|
$q[0]:4$
|
|
|
$q[1]:6$
|
|
|
$q[2]:7$
|
|
|
现在来了一个$a[i]=5$,我们肯定要修改$q[1]=5$,变为：
|
|
|
|
|
|
$q[0]:4$
|
|
|
$q[1]:5$
|
|
|
$q[2]:7$
|
|
|
原来的数组是 **单调上升** 的，修改后也依然是 **单调上升** 的。
|
|
|
|
|
|
既然有这个规律，那么就可以使用二分快速查找大于等于$a[i]$的位置$p$了：
|
|
|
|
|
|
```cpp {.line-numbers}
|
|
|
#include <bits/stdc++.h>
|
|
|
using namespace std;
|
|
|
|
|
|
const int N = 1010;
|
|
|
|
|
|
int a[N], f[N]; // 每个导弹的高度，f[i]:以a[i]结尾的最长不升子序列长度
|
|
|
int q[N], ql; // 需要ql套拦截系统，每个拦截系统最后一个拦截高度为q[i]
|
|
|
int n, res;
|
|
|
|
|
|
int main() {
|
|
|
while (cin >> a[n]) n++;
|
|
|
// 第一问
|
|
|
for (int i = 0; i < n; i++) {
|
|
|
f[i] = 1;
|
|
|
for (int j = 0; j < i; j++)
|
|
|
if (a[i] <= a[j]) // 如果前面的比当前的大，说明是不升序列
|
|
|
f[i] = max(f[i], f[j] + 1);
|
|
|
res = max(res, f[i]);
|
|
|
}
|
|
|
// 第二问
|
|
|
for (int i = 0; i < n; i++) {
|
|
|
int p = lower_bound(q, q + ql, a[i]) - q;
|
|
|
if (p == ql) // 如果没有找到可以接在后面的导弹拦截系统，那么需要创建一套新的拦截系统
|
|
|
q[ql++] = a[i];
|
|
|
else
|
|
|
q[p] = a[i]; // 否则就直接接到找到的第k套拦截系统的后面,那么，第k套拦截系统的最后一个拦截高度=q[k]=h[i]
|
|
|
}
|
|
|
// 输出最长不升序列长度,即：最多能拦截的导弹数
|
|
|
printf("%d\n%d\n", res, ql);
|
|
|
return 0;
|
|
|
}
|
|
|
```
|
|
|
|
|
|
**[$AcWing$ $187$. 导弹防御系统](https://www.acwing.com/problem/content/189/)**
|
|
|
|
|
|
导弹拦截系统的拦截高度即可以 严格单调上升，又可以严格单调下降，此时，用$LIS$模型是无法解决问题的，考虑到$n<50$，可以用$dfs+$剪枝
|
|
|
|
|
|
```cpp {.line-numbers}
|
|
|
#include <bits/stdc++.h>
|
|
|
|
|
|
using namespace std;
|
|
|
const int N = 55;
|
|
|
const int INF = 0x3f3f3f3f;
|
|
|
int n;
|
|
|
int a[N];
|
|
|
int up[N], down[N];
|
|
|
int res;
|
|
|
|
|
|
// 本题关键字：贪心+爆搜
|
|
|
|
|
|
/*
|
|
|
功能：暴搜所有可能，配合剪枝，找出最少的拦截系统数量
|
|
|
u: 第几个导弹
|
|
|
ul: 上升拦截系统的数量，配合up 数组使用
|
|
|
dl: 下降拦截系统的数量，配合down数组使用
|
|
|
*/
|
|
|
void dfs(int u, int ul, int dl) {
|
|
|
if (ul + dl >= res) return; // 伟大的剪枝，不剪枝会TLE~,中途发现已经大于等于res的情况，就返回
|
|
|
if (u == n) { // 走完全程,收集答案
|
|
|
res = min(res, ul + dl); // 因为上面的剪枝，把ul+dl>=res的全干掉了，能到这里的，都是<res的，都可以用来更新答案
|
|
|
return;
|
|
|
}
|
|
|
|
|
|
// 放入上升序列
|
|
|
int k = 0;
|
|
|
// 如果把当前导弹使用上升序列的拦截系统进行拦截，那个选择哪个系统呢？
|
|
|
for (k = 0; k < ul; k++)
|
|
|
if (up[k] <= a[u]) break; // up[0],up[1],up[2],... 这样套拦截系统，其数值来讲，是递减的，因为是因为不能再拦截高度更低的才创建了一套新的拦截系统
|
|
|
// 找出放到哪个拦截系统上去，结果为k
|
|
|
|
|
|
int t = up[k]; // 尝试在第k套系统进行拦截第u个导弹,那么，第u个导弹的高度就是第k套系统的新高度
|
|
|
up[k] = a[u]; // 问题是，我们也不一定非得让第u个导弹使用上升序列拦截系统，也可能使用下降序列拦截系统，所以需要记录当前值，回溯后，尝试下降序列拦截
|
|
|
|
|
|
if (k < ul) // 如果当前这些套拦截系统中可以找到某一套进行拦截
|
|
|
dfs(u + 1, ul, dl); // 接到了某个队伍后面去了，修改队伍的最后最大值即可，队伍数量没有长大
|
|
|
else // 如果当前这些套拦截系统中无法找到某一套进行拦截
|
|
|
dfs(u + 1, ul + 1, dl); // 没有找到任何一个符合最后一个高度小于a[u]的队伍，只能多开一队，up数组长度长大1
|
|
|
|
|
|
up[k] = t; // 回溯
|
|
|
|
|
|
// ----------------------------------------------------------------------
|
|
|
|
|
|
// 放入下降序列
|
|
|
k = 0;
|
|
|
for (k = 0; k < dl; k++)
|
|
|
if (down[k] >= a[u]) break;
|
|
|
|
|
|
t = down[k]; // 保留现场
|
|
|
down[k] = a[u];
|
|
|
if (k < dl)
|
|
|
dfs(u + 1, ul, dl);
|
|
|
else
|
|
|
dfs(u + 1, ul, dl + 1);
|
|
|
down[k] = t; // 回溯
|
|
|
}
|
|
|
|
|
|
int main() {
|
|
|
while (cin >> n, n) { // 多套数据，输入n=0时停止
|
|
|
for (int i = 0; i < n; i++) cin >> a[i];
|
|
|
res = INF; // 防御系统的最少数量
|
|
|
dfs(0, 0, 0); // 开始深搜，更新res的值
|
|
|
printf("%d\n", res);
|
|
|
}
|
|
|
return 0;
|
|
|
}
|
|
|
|
|
|
```
|
|
|
|
|
|
|
|
|
**[$AcWing$ $272$. 最长公共上升子序列](https://www.acwing.com/problem/content/274/)**
|
|
|
|
|
|
|
|
|
```cpp {.line-numbers}
|
|
|
#include <bits/stdc++.h>
|
|
|
using namespace std;
|
|
|
|
|
|
const int N = 3010;
|
|
|
int a[N], b[N];
|
|
|
int f[N][N];
|
|
|
int res;
|
|
|
// 通过了 10/13个数据
|
|
|
// O(n^3)
|
|
|
int main() {
|
|
|
int n;
|
|
|
cin >> n;
|
|
|
for (int i = 1; i <= n; i++) cin >> a[i];
|
|
|
for (int i = 1; i <= n; i++) cin >> b[i];
|
|
|
|
|
|
for (int i = 1; i <= n; i++)
|
|
|
for (int j = 1; j <= n; j++) {
|
|
|
// ① 二维DP打表的一般套路，都是可以直接从上一行继承的
|
|
|
// ② 从题意出发，就是a中前i个数字，b中前j个数字，且以b[j]结尾的子序列中长度最大的
|
|
|
// 那么，a中多整出一个数字来，最起码也是f[i-1][j]的值，不能更小
|
|
|
f[i][j] = f[i - 1][j];
|
|
|
// ③ 如果恰好 a[i]==b[j],那么就可以发生转移
|
|
|
if (a[i] == b[j]) {
|
|
|
int mx = 1; // 最起码a[i]==b[j]，有一个数字是一样嘀~
|
|
|
// f[i-1]是肯定的了，问题是b的前驱在哪里？需要枚举1~j-1
|
|
|
for (int k = 1; k < j; k++)
|
|
|
if (a[i] > b[k]) // j可以接在k后面，那么可能的最大值为f[i-1][k]+1
|
|
|
mx = max(mx, f[i - 1][k] + 1);
|
|
|
// 更新答案
|
|
|
f[i][j] = max(f[i][j], mx);
|
|
|
}
|
|
|
}
|
|
|
int res = 0;
|
|
|
// a数组肯定是火力全开到n就行，b数组中的位置就需要枚举了
|
|
|
for (int i = 1; i <= n; i++) res = max(res, f[n][i]);
|
|
|
printf("%d\n", res);
|
|
|
return 0;
|
|
|
}
|
|
|
```
|
|
|
前面之所以把$b[j]$换成$a[i]$,是因为方便现在考虑。
|
|
|
|
|
|
由于在枚举计算$f[i][j]$时，却用到的是和内层循环（即$b[j]$）无关的，只和外层循环（即$a[i]$）有关，而我们在计算$f[i][j]$，每次都要用到前$j−1$个数中小于$a[i]$的$f[i-1][k]$最大值，所以我们可以用一个变量$mx$不断更新它来保存前$j−1$的答案,就可以避免重复计算，从而降低时间复杂度。
|
|
|
|
|
|
$O(N^2)$
|
|
|
|
|
|
```cpp {.line-numbers}
|
|
|
#include <bits/stdc++.h>
|
|
|
|
|
|
using namespace std;
|
|
|
const int N = 3010;
|
|
|
int a[N], b[N];
|
|
|
int f[N][N];
|
|
|
int res;
|
|
|
|
|
|
// O(n^2)
|
|
|
// f[i][j]—集合：考虑 a 中前 i 个数字，b 中前 j 个数字 ，且当前以 b[j] 结尾的子序列的方案
|
|
|
int main() {
|
|
|
int n;
|
|
|
cin >> n;
|
|
|
for (int i = 1; i <= n; i++) cin >> a[i];
|
|
|
for (int i = 1; i <= n; i++) cin >> b[i];
|
|
|
|
|
|
for (int i = 1; i <= n; i++) {
|
|
|
int mx = 1; // 如果a[i]==b[j],那么LICS最小是1.如果下面的循环中没有一个if被执行，则mx没使上
|
|
|
for (int j = 1; j <= n; j++) {
|
|
|
f[i][j] = f[i - 1][j]; // 先继承过来，现实含义：即使a[i]!=b[j],那么最长长度不会因为i的增加而变化，即f[i][j]=f[i-1][j]
|
|
|
if (a[i] == b[j]) f[i][j] = mx;
|
|
|
if (a[i] > b[j]) mx = max(mx, f[i - 1][j] + 1);
|
|
|
}
|
|
|
}
|
|
|
|
|
|
for (int i = 1; i <= n; i++) res = max(res, f[n][i]);
|
|
|
printf("%d\n", res);
|
|
|
|
|
|
return 0;
|
|
|
}
|
|
|
```
|
|
|
[最长上升子序列 ($LIS$) 详解+例题模板 (全)](https://blog.csdn.net/lxt_Lucia/article/details/81206439)
|
