【算法|动态规划 | 线性dp | 最长上升子序列模型No.1】AcWing1017.怪盗基德的滑翔翼 AcWing1014.登山

个人主页：兜里有颗棉花糖
欢迎 点赞👍 收藏✨ 留言✉ 加关注💓本文由 兜里有颗棉花糖 原创
收录于专栏【AcWing算法提高学习专栏】
🍔本专栏旨在提高自己算法能力的同时，记录一下自己的学习过程，希望对大家有所帮助
🍓希望我们一起努力、成长，共同进步。

一、AcWing1017.怪盗基德的滑翔翼

原题链接：点击直接跳转到该题目

解题代码

#include<iostream>
#include<vector>
using namespace std;const int N = 110;
int arr[N];int main()
{int K;cin >> K;while(K--){int res = 1;int n;scanf("%d",&n);for(int i = 1;i <= n;i++) scanf("%d",&arr[i]);//创建dp表vector<int> dp1(N,1);//正向求解for(int i = 2;i <= n;i++){for(int j = 1;j < i;j++)if(arr[i] > arr[j]) dp1[i] = max(dp1[i],dp1[j] + 1);res = max(dp1[i],res);}//反向求解vector<int> dp2(N,1);for(int i = n - 1;i >= 1;i--){for(int j = n;j > i;j--)if(arr[j] < arr[i]) dp2[i] = max(dp2[i],dp2[j] + 1);res = max(dp2[i],res);}printf("%d\n",res);}return 0;
}

二、AcWing1014.登山

原题链接：点击直接跳转到该题目

解题代码

#include<iostream>
#include<vector>
using namespace std;const int N = 1010;
int arr[N];int main()
{int n;scanf("%d",&n);for(int i = 1;i <= n;i++) cin >> arr[i];// 创建dp表vector<int> dp1(N,1),dp2(N,1);for(int i = 2;i <= n;i++){for(int j = 1;j < i;j++){if(arr[i] > arr[j]) dp1[i] = max(dp1[i],dp1[j] + 1);}}for(int i = n - 1;i >= 1;i--){for(int j = n;j > i;j--){if(arr[i] > arr[j]) dp2[i] = max(dp2[i],dp2[j] + 1);}}vector<int> dp(N);int ret = 0;for(int i = 1;i <= n;i++){dp[i] = dp1[i] + dp2[i] - 1;ret = max(ret,dp[i]);}printf("%d\n",ret);return 0;
}

三、AcWing482.合唱队形

原题链接：点击直接跳转到该题目

解题代码

#include<iostream>
#include<vector>
using namespace std;const int N = 110;
int arr[N];int main()
{int n;scanf("%d",&n);for(int i = 1;i <= n;i++) scanf("%d",&arr[i]);// 创建dp表vector<int> dp1(N,1),dp2(N,1);for(int i = 2;i <= n;i++){for(int j = 1;j < i;j++){if(arr[i] > arr[j]) dp1[i] = max(dp1[i],dp1[j] + 1);}}for(int i = n - 1;i >= 1;i--){for(int j = n;j > i;j--){if(arr[i] > arr[j]) dp2[i] = max(dp2[i],dp2[j] + 1);}}vector<int> dp(N);int res = 0;for(int i = 1;i <= n;i++) dp[i] = dp1[i] + dp2[i] - 1,res = max(res,dp[i]);printf("%d\n",n - res);return 0;
}