AcWing 1.2.1 最长上升子序列模型 + 动态规划 + 图解（详细）

（1）acwing 4557. 最长上升子序列 4557. 最长上升子序列 - AcWing题库

给定一个长度为 N 的整数序列 a1,a2,…,aN。请你计算该序列的最长上升子序列的长度。上升子序列是指数值严格单调递增的子序列

输入格式

第一行包含整数 N
第二行包含 N个整数 a1,a2,…,aN

输出格式

一行，一个整数，表示最长上升子序列的长度

数据范围

1≤N≤1000
0≤ai≤100000

输入样例：

7
1 7 3 5 9 4 8

输出样例：

C++代码：

#include <iostream>
#include <algorithm>
using namespace std;const int N = 1010;int n,res=0;
int arr[N],dp[N];int main() {scanf("%d",&n);for(int i=1;i<=n;i++) scanf("%d",&arr[i]);for(int i=1;i<=n;i++) {dp[i]=1;for(int j=1;j<i;j++) {if(arr[j]<arr[i]) dp[i] = max(dp[i],dp[j]+1);}if (res < dp[i]) res = dp[i]; // 取长的子序列}printf("%d\n",res);return 0;
}

也可以这样写：

int main() {scanf("%d",&n);for(int i=0;i<n;i++) scanf("%d",&arr[i]);dp[0]=1;for(int i=1;i<n;i++) {dp[i]=1;for(int j=0;j<i;j++) {if(arr[j]<arr[i]) dp[i] = max(dp[i],dp[j]+1);}if (res < dp[i]) res = dp[i]; // 取长的子序列}printf("%d\n",res);return 0;
}======================================================int main() {scanf("%d",&n);for(int i=1;i<=n;i++) scanf("%d",&arr[i]);dp[1]=1;for(int i=2;i<=n;i++) {dp[i]=1;for(int j=1;j<i;j++) {if(arr[j]<arr[i]) dp[i] = max(dp[i],dp[j]+1);}if (res < dp[i]) res = dp[i]; // 取长的子序列}printf("%d\n",res);return 0;
}

（2）acwing1017-怪盗基德的滑翔翼

假设城市中一共有 N幢建筑排成一条线，每幢建筑的高度各不相同。初始时，怪盗基德可以在任何一幢建筑的顶端。他可以选择一个方向逃跑，但是不能中途改变方向（因为中森警部会在后面追击）。因为滑翔翼动力装置受损，他只能往下滑行（即：只能从较高的建筑滑翔到较低的建筑）。他希望尽可能多地经过不同建筑的顶部，这样可以减缓下降时的冲击力，减少受伤的可能性。请问，他最多可以经过多少幢不同建筑的顶部(包含初始时的建筑)？

输入格式

输入数据第一行是一个整数K，代表有K组测试数据
每组测试数据包含两行：第一行是一个整数N，代表有N幢建筑。第二行包含N个不同的整数，每一个对应一幢建筑的高度h，按照建筑的排列顺序给出

输出格式

对于每一组测试数据，输出一行，包含一个整数，代表怪盗基德最多可以经过的建筑数量

数据范围

1≤K≤100,
1≤N≤100,
0<h<10000

输入样例：

3
8
300 207 155 299 298 170 158 65
8
65 158 170 298 299 155 207 300
10
2 1 3 4 5 6 7 8 9 10

输出样例：

6
6
9

思路：移动方向一旦确定，就转换成了LIS问题，那么可以看作是两个方向的最长上升子序列问题，答案res为正向和逆向LIS两个过程中的较大者。

C++代码：

// 当确定完方向和起点后，最长的距离是什么呢？
// 起点：a[i]
// 最长距离：以a[i]为结尾的最长上升子序列#include <iostream>
#include <algorithm>using namespace std;const int N = 110;int n;
int arr[N],dp[N];int main() {int T;scanf_s("%d", &T);while (T--) {scanf_s("%d", &n);for (int i = 1; i <= n; i++) scanf_s("%d", &arr[i]);// 正向求解LIS问题int res = 0;for (int i = 1; i <= n; i++) {dp[i] = 1;for (int j = 1; j < i; j++) {if (arr[i] > arr[j]) dp[i] = max(dp[i], dp[j] + 1);}res = max(res, dp[i]);}// 反向求解LIS问题for (int i = n; i>=1; i--) {dp[i] = 1;for (int j = n; j > i; j--) {if (arr[i] > arr[j]) dp[i] = max(dp[i], dp[j] + 1);}res = max(res, dp[i]);}printf("%d\n", res);}return 0;
}

（3）acwing1014-登山问题

五一到了，ACM队 组织大家去登山观光，队员们发现山上一共有N个景点，并且决定按照顺序来浏览这些景点，即每次所浏览景点的编号都要大于前一个浏览景点的编号。同时队员们还有另一个登山习惯，就是不连续浏览海拔相同的两个景点，并且一旦开始下山，就不再向上走了。队员们希望在满足上面条件的同时，尽可能多的浏览景点，你能帮他们找出最多可能浏览的景点数么？

输入格式

第一行包含整数N，表示景点数量
第二行包含N个整数，表示每个景点的海拔

输出格式

输出一个整数，表示最多能浏览的景点数

数据范围

2≤N≤1000

输入样例

8
186 186 150 200 160 130 197 220

输出样例

本题实质上是求正向和反向两次LIS问题，两次的LIS过程相互独立，故所求为两端LIS过程中最长上升子序列的最大长度之和

res = max(res,f[i]+g[i]-1)

C++代码：

/*条件1：按照编号递增的顺序来浏览 => 必须是子序列条件2：相邻两个景点不能相同条件3：一旦开始下降，就不能上升了目标：求最多能浏览多少景点
*/#include <iostream>
#include <algorithm>using namespace std;
const int N = 1010;int n;
int arr[N];
int f[N], g[N];int main() {scanf_s("%d", &n);for (int i = 1; i <= n; i++) scanf_s("%d", &arr[i]);for (int i = 1; i <= n; i++) {f[i] = 1;for (int j = 1; j < i; j++) {if (arr[i] > arr[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 (arr[i] > arr[j]) g[i] = max(g[i], g[j] + 1);}}int res = 0;for (int i = 1; i <= n; i++) res = max(res, f[i] + g[i] - 1);printf("%d\n", res);return 0;
}

（4）acwing 482.合唱队形 482. 合唱队形 - AcWing题库

N 位同学站成一排，音乐老师要请其中的 (N−K) 位同学出列，使得剩下的 K 位同学排成合唱队形。合唱队形是指这样的一种队形：设 K 位同学从左到右依次编号为 1，2…，K 他们的身高分别为 T1，T2，…，TK 则他们的身高满足 T1<…<Ti>Ti+1>…>TK(1≤i≤K)。你的任务是，已知所有 N 位同学的身高，计算最少需要几位同学出列，可以使得剩下的同学排成合唱队形。

输入格式

输入的第一行是一个整数 N ，表示同学的总数
第二行有 N 个整数，用空格分隔，第 i 个整数 Ti 是第 i 位同学的身高(厘米)

输出格式

输出包括一行，这一行只包含一个整数，就是最少需要几位同学出列

数据范围

2≤N≤100
130≤T≤230

思路：如果要使得出列的同学数量最少的话，就意味着要使剩下的数量最多。那意思就是要找到一个先上升再下降的序列，选个最大的。然后再用总数减去这个长度。

#include <iostream>
#include <algorithm>using namespace std;
const int N = 1010;int n;
int arr[N];
int f[N],g[N];int main() {scanf("%d", &n);for (int i = 1; i <= n; i++) scanf("%d", &arr[i]);for(int i=1;i<=n;i++) {f[i] = 1;for(int j=1;j<i;j++) {if(arr[i]>arr[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(arr[i]>arr[j]) g[i] = max(g[i], g[j] + 1);}}int res=0;for(int i=1;i<=n;i++) res = max(res,f[i]+g[i]-1);printf("%d",n-res);return 0;
}

（5）acwing 1012.友好城市

输入样例：

输出样例：

>>思路和分析

对于任意一种合法的建立桥梁的方式，都可以对应一种因变量的上升子序列。反之，对于因变量的任何一个上升子序列，我们都可以唯一的对应一个合法的建桥方式。每一种建桥方式，建桥的数量和上升子序列的长度是相同的。因此左边集合（所有合法的建桥方式）的长度最大值就等于右边集合（上升子序列）的长度的最大值。
解法：先按照自变量的大小，把因变量排序。排好之后得到一个序列，然后在序列当中求最长的一个上升子序列。
排序思路：看一下什么会出现相交的情况？
本质：如果选出来的桥梁是没有交叉的，那么就意味着按照其中某一个点来排序，那么另外一个点对应的位置也一定要使有序的才可以。因为一旦出现逆序，就是有交叉的。没有交叉也就意味着一定没有逆序的。那本题其实就可以转化为求最长上升子序列的长度。

C++代码：

#include <iostream>
#include <algorithm>using namespace std;typedef pair<int, int> PII;const int N = 5010;int n;
PII q[N];
int f[N];int main() {scanf_s("%d", &n);for (int i = 0; i < n; i++) scanf_s("%d%d", &q[i].first, &q[i].second);sort(q, q + n);int res = 0;for (int i = 0; i < n; i++) {f[i] = 1;for (int j = 0; j < i; j++) {if (q[i].second > q[j].second) f[i] = max(f[i], f[j] + 1);}res = max(res, f[i]);}printf("%d\n",res);return 0;
}

（6）acwing 1016.最长上升子序列和

输入样例：

7
1 7 3 5 9 4 8

输出样例：

C++代码：

#include <iostream>
#include <algorithm>using namespace std;const int N = 1010;
int n;
int a[N], f[N];int main() {scanf_s("%d", &n);for (int i = 1; i <= n; i++) scanf_s("%d", &a[i]);for (int i = 1; i <= n; i++) {f[i] = a[i];for (int j = 1; j <i; j++) {if (a[i] > a[j]) f[i] = max(f[i], f[j] + a[i]);}}int res = 0;for (int i = 1; i <= n; i++) res = max(res, f[i]);printf("%d\n", res);return 0;
}