文章目录
一、前言
二、AcWing 1017. 怪盗基德的滑翔翼
1.题目
2.逻辑解释
3.AC代码
三、AcWing 1014. 登山
1.题目
2.逻辑解释
3.AC代码
四、AcWing 482. 合唱队形
1.题目
2.逻辑解释
3.AC代码
五、AcWing 1012. 友好城市
1.题目
2.逻辑解释
3.AC代码
六、AcWing 1016. 最大上升子序列和
1.题目
2.逻辑解释
3.AC代码
七、AcWing 1010. 拦截导弹
1.题目
2.逻辑解释
3.AC代码
八、AcWing 187. 导弹防御系统
1.题目
2.逻辑解释
3.AC代码
九、AcWing 272. 最长公共上升子序列
1.题目
2.AC代码
十、额外的练习题
一、前言
AcWing算法提高课内容，本文讲解 动态规划
本篇包括以下题目：
⭐️AcWing 1017. 怪盗基德的滑翔翼
⭐️AcWing 1014. 登山
⭐️AcWing 1017. AcWing 1012. 友好城市
⭐️AcWing 1017. AcWing 1016. 最大上升子序列和
⭐️AcWing 1017. AcWing 1010. 拦截导弹
⭐️AcWing 1017. AcWing 187. 导弹防御系统
⭐️AcWing 1017. AcWing 272. 最长公共上升子序列
写博客有哪里不完善的地方或者有哪里表达错误希望大家提出来，博主会立即改正！望大家海涵
文末附有几道练习题目，读者在看懂上述题目之后可以拿来练手，题目链接为本人博客(博客中有原题链接)，每道题目均附有题解。
本文需要先自修基础：线性DP
二、AcWing 1017. 怪盗基德的滑翔翼
1.题目
本题链接：怪盗基德的滑翔翼
本博客提供本题截图：
2.逻辑解释
我们把题目抽象一下，其实就是要求一个最长下降子序列，因为题目中说基德可以在任意一个房子的屋顶，所以我们只需要从左往右飞一遍，再从右往左飞一遍，两遍去最大值即可.
3.AC代码
#include <iostream> #include <algorithm> using namespace std; const int N = 110; int h[N], f[N]; int main() { int t; cin >> t; while (t -- ) { int n; cin >> n; for (int i = 0; i < n; i ++ ) cin >> h[i]; int res = 0; for (int i = 0; i < n; i ++ ) //n个房子依次遍历，往左飞 { f[i] = 1; for (int j = 0; j < i; j ++ ) if (h[j] < h[i]) f[i] = max(f[i], f[j] + 1); res = max(res, f[i]); } for (int i = n - 1; ~i; i -- ) //n个房子依次遍历，往右飞 { f[i] = 1; for (int j = n - 1; j > i; j -- ) if (h[j] < h[i]) f[i] = max(f[i], f[j] + 1); res = max(res, f[i]); } cout << res << endl; } return 0; }
三、AcWing 1014. 登山
1.题目
本题链接：登山
本博客提供本题截图：
2.逻辑解释
题目抽象后，本题其实就是求一个先上升再下降的序列的最大值，和上题思路其实一致，先做一次最长上升子序列f[i]再做一次最长下降子序列g[i]，最后按照第 i个点分开求 max(f[i] + g[i] - 1)
3.AC代码
#include <iostream> #include <algorithm> using namespace std; const int N = 1010; int h[N], f[N], g[N]; int main() { int n; cin >> n; for (int i = 1; i <= n; i ++ ) cin >> h[i]; for (int i = 1; i <= n; i ++) { f[i] = 1; for (int j = 1; j < i; j ++ ) if (h[j] < h[i]) f[i] = max(f[i], f[j] + 1); } for (int i = n; i; i -- ) { g[i] = 1; for (int j = n; j > i; j -- ) if (h[j] < h[i]) 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); cout << res << endl; return 0; }
