算法提高课第一章上升子序列模型-CSDN博客

本文链接：https://blog.csdn.net/csdn_ggboy/article/details/121431546

本文通过多个AcWing题库实例介绍了如何运用动态规划解决最长上升子序列等问题，包括求解最长上升子序列、最友好友城市等典型题目。

摘要生成于 C知道，由 DeepSeek-R1 满血版支持，前往体验 >

基本模型：使用动态规划解决最长上升子序列问题, 核心是用以 $i$ 为结尾的序列来表示所有满足要求的集合

1017. 怪盗基德的滑翔翼 - AcWing题库

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;
const int N = 110;
int dp1[N], dp2[N];//以i结尾的上升子序列的长度
int a[N];
int n;
int main()
{
    int t;
    cin >> t;
    while(t -- )
    {
        cin >> n;
        for(int i = 1; i <= n; i ++ )
        {
            cin >> a[i];
            dp1[i] = 1, dp2[i] = 1;
        }
        for(int i = 1; i <= n; i ++ )
        for(int j = 1; j < i; j ++ )
        {
            if(a[i] > a[j])
                dp1[i] = max(dp1[i], dp1[j] + 1);
            else if(a[i] < a[j])
                dp2[i] = max(dp2[i], dp2[j] + 1);
            
        }
        int ans = 0;
        for(int i = 1; i <= n ; i ++ )
        {
            ans = max({ans, dp1[i], dp2[i]});
        }
        cout << ans << endl;
    }
}

1014. 登山 - AcWing题库

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;
int n;
int dp[1010][2];//dp[i][0]以i结尾的上升序列，dp[i][1]以i结尾的下降序列
int a[1010];
int main()
{
    
    //最长的不连续，一次下山，不能再上山。
    cin >> n;
    for(int i = 1; i <= n; i ++ )
        cin >> a[i], dp[i][0] = 1;
    for(int i = 1; i <= n; i ++ )
    for(int j = 1; j < i; j ++ )
    {
        if(a[i] > a[j])
            dp[i][0] = max(dp[i][0], dp[j][0] + 1);
        else if(a[i] < a[j])
            dp[i][1] = max({dp[i][1], dp[j][0] + 1, dp[j][1] + 1});
    }
    int ans = 0;
    for(int i = 1; i <= n; i ++ )
        ans = max({ans, dp[i][0], dp[i][1]});
    cout << ans << endl;
}

482. 合唱队形 - AcWing题库

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;
const int N = 110;
int dp[N][2];
int n;
int a[N];
int main()
{
    //上升---下降
    cin >> n;
    for(int i = 1; i <= n; i ++ ) cin >> a[i], dp[i][0] = 1;
    
    for(int i = 1; i <= n; i ++ )
    for(int j = 1; j < i; j ++ )
    {
        if(a[i] > a[j])
        {
            dp[i][0] = max(dp[i][0], dp[j][0] + 1);
        }
        else if(a[i] < a[j])
        {
            dp[i][1] = max({dp[i][1], dp[j][0] + 1, dp[j][1] + 1});
        }
    }
    int ans = 0;
    for(int i = 1; i <= n; i ++ )
    {
        ans = max({ans, dp[i][0], dp[i][1]});
    }
    cout << n - ans;
}

1012. 友好城市 - AcWing题库

#include <iostream>
#include <cstring>
#include <algorithm>
#define PII pair<int, int>
#define y second
#define x first

using namespace std;
vector<PII> g;
int n;
int dp[5010];
int main()
{
    //最长的一个序列，满足 a1 < a2 && b1 < b2
    //可以先按一个顺序排序，然后求最长上升序列。
    cin >> n;
    for(int i = 1; i <= n; i ++ )
    {
        int a, b;
        cin >> a >> b;
        g.push_back({a, b});
        dp[i] = 1;
    }
    sort(g.begin(), g.end());
    for(int i = 1; i <= n; i ++ )
    for(int j = 1; j < i; j ++ )
    {
        if(g[i - 1].y > g[j - 1].y)
            dp[i] = max(dp[i], dp[j] + 1);
    }
    int ans = 0;
    for(int i = 1; i <= n; i++ ) ans = max(ans, dp[i]);
    cout << ans;

}

1016. 最大上升子序列和 - AcWing题库

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;
const int N = 1100;
int a[N];
int dp[N];
int n;
int main()
{
    
    cin >> n;
    for(int i = 1; i <= n; i++ ) cin >> a[i], dp[i] = a[i];
    
    for(int i = 1; i <= n; i ++ )
    for(int j = 1; j < i; j ++ )
    {
        if(a[i] > a[j])
            dp[i] = max(dp[i], dp[j] + a[i]);
    }
    int ans = 0;
    for(int i = 1; i <= n; i ++ ) ans = max(ans, dp[i]);
    cout << ans << endl;
}

1010. 拦截导弹 - AcWing题库

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;
const int N = 1100;
int a[N];
int dp[N][2];
int main()
{
    int cnt = 0;
    while(true)
    {
        cin >> a[++ cnt];
        if(!a[cnt])
        {
            cnt --;
            break;
        }
    }
    for (int i = 1; i <= cnt; i ++ ) dp[i][0] = 1, dp[i][1] = 1;
    for(int i = 1; i <= cnt; i ++ )
    for(int j = 1; j < i; j ++ )
    {
        if(a[i] <= a[j])
            dp[i][0] = max(dp[i][0], dp[j][0] + 1);
        else 
            dp[i][1] = max(dp[i][1], dp[j][1] + 1);
    }
    int ans1 = 0, ans2 = 0;
    for(int i = 1; i <= cnt; i ++ )
    {
        ans1 = max(ans1, dp[i][0]);
        ans2 = max(ans2, dp[i][1]);
    }
    cout << ans1 << endl;
    cout << ans2 << endl;
}