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

一、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;
}