最长上升子序列模型

题目1: 怪盗基德的滑翔翼

对于这道题目而言， 我们可以正序( 从(0 ~ n - 1) ) 求一遍最长上升子序列， 维护一个最大值。 然后再倒序( 从(n - 1 ~ 0) ) 求一遍最长上升子序列， 并尝试使用更新的f(i)去更新我们的最大值，最后将最大值输出即可。

因为f(i)表示以a(i)结尾的最长上升子序列的长度， 所以f(i)可以全部初始化成1

因为这里没有涉及到i - 1, 不会发生数组下标是负数的情况， 所以数组下标从0开始还是从1开始并不重要。

时间复杂度： O ( n 2 ) O(n^2) O(n2) 量级：1e4, 1秒之内可以出解

代码区

#include
#include

using namespace std;

const int N = 110;

int n;
int a[N];
int f[N];

int main()
{
    int t;
    cin >> t;
    while(t --)
    {
        cin >> n;
        for(int i = 0; i < n; i ++) cin >> a[i];
        
        int res = 0;
        for(int i = 0; i < n; i ++)
        {
            f[i] = 1;
            for(int j = 0; j < i; j ++)
            {
                if(a[i] > a[j])
                f[i] = max(f[i], f[j] + 1);
            }
            res = max(res, f[i]);
        }
        
        memset(f, 0, sizeof f);
        for(int i = n - 1; i >= 0; i --)
        {
            f[i] = 1;
            for(int j = n - 1; j > i; j --)
            {
                if(a[i] > a[j])
                {
                    f[i] = max(f[i], f[j] + 1);
                }
            }
            res = max(res, f[i]);
        }
        cout << res << endl;
    }
    
    return 0;
}

题目2: 登山

分别从0 ~ n - 1 做一遍最长上升子序列和从 n - 1 ~ 0做一遍最长上升子序列， 结果分别保存在f(i) 和 g(i)中， 最后从前往后遍历一遍求出f(i) + g(i) - 1 的最大值， 输出最大值即可。

时间复杂度： O ( n 2 ) O(n ^ 2) O(n2) 量级：1e6, 1秒之内可以出解

代码区：

#include
#include

using namespace std;

const int N = 1010;

int n;
int a[N];
int f[N], g[N];

int main()
{
    cin >> n;
    for(int i = 0; i < n; i ++) cin >> a[i];
    
    for(int i = 0; i < n; i ++)
    {
        f[i] = 1;
        for(int j = 0; j < i; j ++)
        {
            if(a[i] > a[j])
            {
                f[i] = max(f[i], f[j] + 1);
            }
        }
    }
    
    for(int i = n - 1; i >= 0; i --)
    {
        g[i] = 1;
        for(int j = n - 1; j > i; j --)
        {
            if(a[i] > a[j])
            {
                g[i] = max(g[i], g[j] + 1);
            }
        }
    }
    
    int res = 0;
    for(int i = 0; i < n; i ++)
    {
        res = max(res, f[i] + g[i] - 1);
    }
    
    cout << res << endl;
    
    return 0;
}

题目3: 合唱队形

和登山那题基本一样， 最后输出时做一下改变即可。

时间复杂度： O ( n 2 ) O(n^2) O(n2) 量级1e4, 1秒之内可以出结果

代码区

#include
#include

using namespace std;

const int N = 110;

int n;
int a[N];
int f[N], g[N];

int main()
{
    cin >> n;
    
    for(int i = 0; i < n; i ++) cin >> a[i];
    
    for(int i = 0; i < n; i ++)
    {
        f[i] = 1;
        for(int j = 0; j < i; j ++)
        {
            if(a[i] > a[j])
            f[i] = max(f[i], f[j] + 1);
        }
    }
    
    for(int i = n - 1; i >= 0; i --)
    {
        g[i] = 1;
        for(int j = n - 1; j > i; j --)
        {
            if(a[i] > a[j])
            {
                g[i] = max(g[i], g[j] + 1);
            }
        }
    }
    
    int res = 0;
    for(int i = 0; i < n; i ++) 
    {
        res = max(res, f[i] + g[i] - 1);
    }
    
    cout << n - res << endl;
    
    
    return 0;
}

题目4: 友好城市

观察输入， 给定的是南北两岸的两个城市的坐标， 所以我们可以使用pair进行存储。题目要求：保证任意两条航线不相交的情况下， 所以我们可以按区间南岸的城市进行排序， 然后找出北岸的最长上升子序列的最大长度即为所求的答案。

时间复杂度： O(n^2) 量级为：1e6,1秒之内可以出解

代码区：

#include
#include
#include

using namespace std;

typedef pair PII;

const int N = 5010;

int n;
PII city[N];
int f[N];

int main()
{
    cin >> n;
    for(int i = 0; i < n; i ++)
    {
        cin >> city[i].first >> city[i].second;
    }
    sort(city, city + n);
    
    int res = 0;
    for(int i = 0; i < n; i ++)
    {
        f[i] = 1;
        for(int j = 0; j < i; j ++)
        {
            if(city[i].second > city[j].second)
            {
                f[i] = max(f[i], f[j] + 1);
            }
        }
        res = max(res, f[i]);
    }
    
    cout << res << endl;
    
    return 0;
}

题目5: 最大上升子序列的和

改变一下状态表示即可

时间复杂度： O ( n 2 ) O(n^2) O(n2) 量级：1e6， 1秒之内可以出解

代码区:

#include
#include

using namespace std;

const int N = 1010;

int n;
int a[N];
int f[N];

int main()
{
    cin >> n;
    
    for(int i = 0; i < n; i ++) cin >> a[i];
    
    int res = 0;
    for(int i = 0; i < n; i ++)
    {
        f[i] = a[i];
        for(int j = 0; j < i; j ++)
        {
            if(a[i] > a[j])
            {
                f[i] = max(f[i], f[j] + a[i]);
            }
        }
        res = max(res, f[i]);
    }
    
    cout << res << endl;
    
    return 0;
}

题目6: 拦截导弹

第一小问就是求一个最长下降子序列， 第二小问可以用贪心来做， 用一个数组 (g[]) 存储每个序列的最后一个元素的值。遍历一遍所有的元素， 如果当前元素比之前的维护的数组g[]中的数值小， 则直接替换该位置的值， 否则将在数组后面开一个新的位置进行存储。

因为每个序列是非严格单调下降序列， 所以g[]数组是严格单调上升的数组

时间复杂度： O ( n 2 ) O(n^2) O(n2) 量级：1e6, 1秒之内可以出解

代码区：

#include
#include

using namespace std;

const int N = 1010;

int h[N], cnt;
int g[N];
int f[N];

int main()
{
    int a;
    while(cin >> a)
    {
        h[cnt ++] = a;
    }
    
    int res = 0;
    for(int i = 0; i < cnt; i ++)
    {
        f[i] = 1;
        for(int j = 0; j < i; j ++)
        {
            if(h[i] <= h[j] )
            f[i] = max(f[i], f[j] + 1);
        }
        res = max(res, f[i]);
    }
    cout << res << endl;
    
    int id = 0;
    for(int i = 0; i < cnt; i ++)
    {
        int k = 0;
        while(k < id && g[k] < h[i] ) k ++;
        g[k] = h[i];
        if(k == id) id ++;
    }
    cout << id << endl;
    
    return 0;
}

题目7: 导弹防御系统

和上一题导弹拦截的贪心策略一样， 不过这题每个元素可能在上升子序列中， 也可能在下降子序列中， 所以要维护两个数组。

时间复杂度： O ( n ∗ 2 n ) O(n * 2^n) O(n∗2n)
代码区：

#include
#include

using namespace std;

const int N = 55;

int n;
int a[N];
int up[N], down[N];
int ans;

void dfs(int u, int us, int ds)
{
    if(us + ds >= ans) return ;
    if(u == n)
    {
        ans = us + ds;
    }
    
    int k = 0;
    while(k < us && up[k] >= a[u]) k ++;
    int temp = up[k];
    up[k] = a[u];
    if(k < us) dfs(u + 1, us, ds);
    else dfs(u + 1, us + 1, ds);
    up[k] = temp;
    
    int cnt = 0;
    while(cnt < ds && down[cnt] <= a[u]) cnt ++;
    int temp1 = down[cnt];
    down[cnt] = a[u];
    if(cnt < ds) dfs(u + 1, us, ds);
    else dfs(u + 1, us, ds + 1);
    down[cnt] = temp1;
    
}

int main()
{
    while(cin >> n, n)
    {
        for(int i = 0; i < n; i ++) cin >> a[i];
        
        ans = n;
        
        dfs(0, 0, 0);
        
        cout << ans << endl;
        
    }
    
    return 0;
}

题目8: 最长公共子序列

因为这里涉及到 i - 1,所以我们的下标从1开始比较方便， 省去从0开始要写的特判。

每个状态都能通过状态转移方程转移过来， 求的是最大值， 初始化成0就可以了。

时间复杂度： o ( n ∗ m ) o(n * m) o(n∗m), 量级1e6， 1秒之内可以出解

代码区：

#include
#include

using namespace std;

const int N = 1010;

int n, m;
char s[N], p[N];
int f[N][N];

int main()
{
    cin >> n >> m;
    cin >> s + 1 >> p + 1;
    
    for(int i = 1; i <= n; i ++)
    {
        for(int j = 1; j <= m; j ++)
        {
            if(s[i] == p[j]) f[i][j] = f[i - 1][j - 1] + 1;
            else 
            {
                f[i][j] = max(f[i][j - 1], f[i - 1][j]);
            }
        }
    }
    
    cout << f[n][m] << endl;
    
    return 0;
}

题目9: 最长公共上升序列

直接引用yxc的题解， 写的真不错hh: 题解

时间复杂度: O ( n 2 ) O(n^2) O(n2), 量级：1e6， 1秒之内可以出解

代码区:

#include
#include

using namespace std;

const int N = 3010;

int n;
int a[N], b[N];
int f[N][N];

int main()
{
    cin >> n;

    for(int i = 1; i <= n; i ++) cin >> a[i];
    for(int i = 1; i <= n; i ++) cin >> b[i];

    for(int i = 1; i <= n; i ++)
    {
        int maxv = 1;
        for(int j = 1; j <= n; j ++)
        {
            f[i][j] = f[i - 1][j];
            if(a[i] == b[j]) f[i][j] = max(f[i][j], maxv);
            if(a[i] > b[j]) maxv = max(maxv, f[i - 1][j] + 1);
        }
    }

    int res = 0;
    for(int i = 1; i <= n; i ++)
    res = max(res, f[n][i]);
    cout << res;
    
    return 0;
}