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

刺骨的言语ヽ痛彻心扉 2024-04-27 06:52 67阅读 0赞

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

#### 目录 ####

*  一、AcWing1017.怪盗基德的滑翔翼
 *   *  解题代码
 *  二、AcWing1014.登山
 *   *  解题代码
 *  三、AcWing482.合唱队形
 *   *  解题代码

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

**原题链接：[点击直接跳转到该题目][Link 2]**

### 解题代码 ###

#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.登山 ##

**原题链接：[点击直接跳转到该题目][Link 3]**

### 解题代码 ###

#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.合唱队形 ##

**原题链接：[点击直接跳转到该题目][Link 4]**

### 解题代码 ###

#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;
    }

[Link 1]: https://xiaofeizhu.blog.csdn.net/
[AcWing]: https://blog.csdn.net/m0_74352571/category_12481646.html
[Link 2]: https://www.acwing.com/problem/content/1019/
[Link 3]: https://www.acwing.com/problem/content/1016/
[Link 4]: https://www.acwing.com/problem/content/484/