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

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

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

    输入格式
    • 第一行包含整数 N
    • 第二行包含 N个整数 a1,a2,…,aN
    输出格式
    • 一行，一个整数，表示最长上升子序列的长度
    数据范围
    • 1≤N≤1000
    • 0≤ai≤100000
    输入样例：
    1. 7
    2. 1 7 3 5 9 4 8
    输出样例：
    4

     C++代码：

    1. #include 
    2. #include 
    3. using namespace std;
    4.  
    5. const int N = 1010;
    6.  
    7. int n,res=0;
    8. int arr[N],dp[N];
    9.  
    10. int main() {
    11.     scanf("%d",&n);
    12.     for(int i=1;i<=n;i++) scanf("%d",&arr[i]);
    13.     for(int i=1;i<=n;i++) {
    14.         dp[i]=1;
    15.         for(int j=1;j
    16.             if(arr[j]
    17.                 dp[i] = max(dp[i],dp[j]+1);
    18.         }
    19.         if (res < dp[i]) res = dp[i]; // 取长的子序列
    20.     }
    21.     printf("%d\n",res);
    22.     return 0;
    23. }

    也可以这样写：

    1. int main() {
    2.     scanf("%d",&n);
    3.     for(int i=0;iscanf("%d",&arr[i]);
    4.     dp[0]=1;
    5.     for(int i=1;i
    6.         dp[i]=1;
    7.         for(int j=0;j
    8.             if(arr[j]
    9.                 dp[i] = max(dp[i],dp[j]+1);
    10.         }
    11.         if (res < dp[i]) res = dp[i]; // 取长的子序列
    12.     }
    13.     printf("%d\n",res);
    14.     return 0;
    15. }
    16.  
    17. ======================================================
    18.  
    19. int main() {
    20.     scanf("%d",&n);
    21.     for(int i=1;i<=n;i++) scanf("%d",&arr[i]);
    22.     dp[1]=1;
    23.     for(int i=2;i<=n;i++) {
    24.         dp[i]=1;
    25.         for(int j=1;j
    26.             if(arr[j]
    27.                 dp[i] = max(dp[i],dp[j]+1);
    28.         }
    29.         if (res < dp[i]) res = dp[i]; // 取长的子序列
    30.     }
    31.     printf("%d\n",res);
    32.     return 0;
    33. }

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

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

    输入格式

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

    输出格式

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

    数据范围

    • 1≤K≤100,
    • 1≤N≤100,
    • 0

    输入样例：

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

    输出样例：

    1. 6
    2. 6
    3. 9

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

     C++代码：

    1. // 当确定完方向和起点后，最长的距离是什么呢？
    2. // 起点：a[i]
    3. // 最长距离：以a[i]为结尾的最长上升子序列
    4.  
    5. #include 
    6. #include 
    7.  
    8. using namespace std;
    9.  
    10. const int N = 110;
    11.  
    12. int n;
    13. int arr[N],dp[N];
    14.  
    15. int main() {
    16. 	int T;
    17. 	scanf_s("%d", &T);
    18. 	while (T--) {
    19. 		scanf_s("%d", &n);
    20. 		for (int i = 1; i <= n; i++) scanf_s("%d", &arr[i]);
    21. 		// 正向求解LIS问题
    22. 		int res = 0;
    23. 		for (int i = 1; i <= n; i++) {
    24. 			dp[i] = 1;
    25. 			for (int j = 1; j < i; j++) {
    26. 				if (arr[i] > arr[j]) dp[i] = max(dp[i], dp[j] + 1);
    27. 			}
    28. 			res = max(res, dp[i]);
    29. 		}
    30. 		// 反向求解LIS问题
    31. 		for (int i = n; i>=1; i--) {
    32. 			dp[i] = 1;
    33. 			for (int j = n; j > i; j--) {
    34. 				if (arr[i] > arr[j]) dp[i] = max(dp[i], dp[j] + 1);
    35. 			}
    36. 			res = max(res, dp[i]);
    37. 		}
    38. 		printf("%d\n", res);
    39. 	}
    40. 	return 0;
    41. }

    （3）acwing1014-登山问题

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

    输入格式

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

    输出格式

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

    数据范围

    • 2≤N≤1000

    输入样例

    1. 8
    2. 186 186 150 200 160 130 197 220

    输出样例

    4

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

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

    C++代码：

    1. /*
    2. 	条件1：按照编号递增的顺序来浏览 => 必须是子序列
    3. 	条件2：相邻两个景点不能相同
    4. 	条件3：一旦开始下降，就不能上升了
    6. 	目标：求最多能浏览多少景点
    7. */
    8.  
    9. #include 
    10. #include 
    11.  
    12. using namespace std;
    13. const int N = 1010;
    14.  
    15. int n;
    16. int arr[N];
    17. int f[N], g[N];
    18.  
    19. int main() {
    20. 	scanf_s("%d", &n);
    21. 	for (int i = 1; i <= n; i++) scanf_s("%d", &arr[i]);
    22. 	for (int i = 1; i <= n; i++) {
    23. 		f[i] = 1;
    24. 		for (int j = 1; j < i; j++) {
    25. 			if (arr[i] > arr[j]) f[i] = max(f[i], f[j] + 1);
    26. 		}
    27. 	}
    28. 	for (int i = n; i >= 1; i--) {
    29. 		g[i] = 1;
    30. 		for (int j = n; j > i; j--) {
    31. 			if (arr[i] > arr[j]) g[i] = max(g[i], g[j] + 1);
    32. 		}
    33. 	}
    34. 	int res = 0;
    35. 	for (int i = 1; i <= n; i++) res = max(res, f[i] + g[i] - 1);
    36. 	printf("%d\n", res);
    37. 	return 0;
    38. }

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

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

    输入格式
    • 输入的第一行是一个整数 N ，表示同学的总数
    • 第二行有 N 个整数，用空格分隔，第 i  个整数 Ti  是第 i 位同学的身高(厘米)
    输出格式
    • 输出包括一行，这一行只包含一个整数，就是最少需要几位同学出列
    数据范围
    • 2≤N≤100
    • 130≤T≤230

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

    1. #include 
    2. #include 
    3.  
    4. using namespace std;
    5. const int N = 1010;
    6.  
    7. int n;
    8. int arr[N];
    9. int f[N],g[N];
    10.  
    11. int main() {
    12.     scanf("%d", &n);
    13.     for (int i = 1; i <= n; i++) scanf("%d", &arr[i]);
    14.     for(int i=1;i<=n;i++) {
    15.         f[i] = 1;
    16.         for(int j=1;j
    17.             if(arr[i]>arr[j]) f[i] = max(f[i], f[j] + 1);
    18.         }
    19.     }
    20.     for(int i=n;i>=1;i--) {
    21.         g[i] = 1;
    22.         for(int j=n;j>i;j--) {
    23.             if(arr[i]>arr[j]) g[i] = max(g[i], g[j] + 1);
    24.         }
    25.     }
    26.     int res=0;
    27.     for(int i=1;i<=n;i++) res = max(res,f[i]+g[i]-1);
    28.     printf("%d",n-res);
    29.     return 0;
    30. }

    （5）acwing 1012.友好城市

    输入样例： 

    1. 7
    2. 22 4
    3. 2 6
    4. 10 3
    5. 15 12
    6. 9 8
    7. 17 17
    8. 4 2

    输出样例： 

    4

     

    >>思路和分析

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

    C++代码： 

    1. #include 
    2. #include 
    3.  
    4. using namespace std;
    5.  
    6. typedef pair<int, int> PII;
    7.  
    8. const int N = 5010;
    9.  
    10. int n;
    11. PII q[N];
    12. int f[N];
    13.  
    14. int main() {
    15. 	scanf_s("%d", &n);
    16. 	for (int i = 0; i < n; i++) scanf_s("%d%d", &q[i].first, &q[i].second);
    17. 	sort(q, q + n);
    18.  
    19. 	int res = 0;
    20. 	for (int i = 0; i < n; i++) {
    21. 		f[i] = 1;
    22. 		for (int j = 0; j < i; j++) {
    23. 			if (q[i].second > q[j].second) f[i] = max(f[i], f[j] + 1);
    24. 		}
    25. 		res = max(res, f[i]);
    26. 	}
    27. 	printf("%d\n",res);
    28. 	return 0;
    29. }

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

    输入样例：  

    1. 7
    2. 1 7 3 5 9 4 8

     输出样例： 

    18

     C++代码：

    1. #include 
    2. #include 
    3.  
    4. using namespace std;
    5.  
    6. const int N = 1010;
    7. int n;
    8. int a[N], f[N];
    9.  
    10. int main() {
    11. 	scanf_s("%d", &n);
    12. 	for (int i = 1; i <= n; i++) scanf_s("%d", &a[i]);
    13. 	for (int i = 1; i <= n; i++) {
    14. 		f[i] = a[i];
    15. 		for (int j = 1; j 
    16. 			if (a[i] > a[j]) f[i] = max(f[i], f[j] + a[i]);
    17. 		}
    18. 	}
    19. 	int res = 0;
    20. 	for (int i = 1; i <= n; i++) res = max(res, f[i]);
    21. 	printf("%d\n", res);
    22. 	return 0;
    23. }
  • 相关阅读:
    《Python进阶系列》二十九：append浅拷贝机制——你真的会用append函数吗？
    怎样选择合适的CRM客户管理系统？
    深入 Qt5 信号槽新语法
    进程与线程的关系，进程调度的基本过程
    你不知道的Set集合
    Redis底层数据结构介绍
    JAVA程序员和C程序员的差距在哪里?
    解决github打开慢的问题
    Python 打包技巧分享：彻底解决 pyinstaller 打包exe文件太大的问题
    算法：数组常见套路1---双指针、取模、打擂台法
  • 原文地址：https://blog.csdn.net/weixin_41987016/article/details/134081304