[AcWing]1017.怪盗基德的滑翔翼（C++实现）最长上升子序列模型

读题&＃xff1a;

1. 只能选择一个方向下降&＃xff0c;可以选则正向、可以选择反向

2. 所选择的楼是呈现单调下降的&＃xff08;反过来就是单调上升的&＃xff09;

即无论正向和反向&＃xff0c;都可以看成求最长上升的子序列&＃xff0c;即在每个节点正向求一遍最长上升子序列、再反向求一遍最长上升子序列&＃xff0c;最后取max得到最大的最长上升子序列即可。

思路&＃xff1a;
在[AcWing] 897. 最长公共子序列&＃xff08;C&＃43;&＃43;实现&＃xff09;线性dp例题的基础上&＃xff0c;只需要在每个节点正向判断一次最长上升子序列&＃xff0c;反向判断一次最长上升子序列&＃xff0c;然后求出最大值即可。

---------------------------------------------------解法---------------------------------------------------

#include
#include
#include
using namespace std;const int N &＃61; 110;
int n;
int h[N];
int f[N];int main(){int K;cin >> K;while(K--){scanf("%d", &n);for (int i &＃61; 0; i < n; i &＃43;&＃43; ) scanf("%d", &h[i]);int res &＃61; 0;// 正向遍历一次求最长上升子序列for (int i &＃61; 0; i < n; i &＃43;&＃43; ){f[i] &＃61; 1;for (int j &＃61; 0; j < i; j &＃43;&＃43; )if (h[j] < h[i])f[i] &＃61; max(f[i], f[j] &＃43; 1);res &＃61; max(res, f[i]);}// 反向遍历一次求最长上升子序列memset(f, 0, sizeof f);for (int i &＃61; n - 1; i >&＃61; 0; i -- ){f[i] &＃61; 1;for (int j &＃61; n - 1; j > i; j -- )if (h[j] < h[i]) f[i] &＃61; max(f[i], f[j] &＃43; 1);res &＃61; max(res, f[i]);}cout << res << endl;}return 0;
}


可能存在的问题

• [AcWing] 897. 最长公共子序列&＃xff08;C&＃43;&＃43;实现&＃xff09;线性dp例题

• 动态规划
• 最长上升子序列问题

最长上升子序列模型&＃xff0c;可以发展为不同的最长上升子序列题目

最长上升子序列模型的特征&＃xff1a;
1. 以每个点为终点都要判断一遍
2. 路径为一条上升子序列&＃xff08;或下降子序列&＃xff09;