最长上升子序列问题一（朴素版）

文章目录

• • 一、裸题
  • 二、怪盗基德的滑翔翼
  • 三、登山
  • 四、合唱队形
  • 五、友好城市
  • 六、最大上升子序列和

一、裸题

题目链接

这个题目很容易，以i结尾的子序列最长是多少，从0到i-1之间遍历

#include<iostream>
using namespace std;
const int N = 1010;
int f[N];
int g[N];
int num[N];
int n;

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

二、怪盗基德的滑翔翼

题目链接

这个题目的关键是怪盗基德可以选择任何一栋建筑从前向后逃跑，或者从后向前，那么怎么样才能让怪盗基德通过的建筑最多？
那么我们必须以怪盗基德到达的某一栋的建筑物作为研究对象

#include<iostream>
#include<algorithm>
using namespace std;
const int N = 110;
int h[N];
int f[N];
int g[N];

int main()
{
    int T;
    cin >> T;
    while(T --)
    {

        int n;
        cin >> n;
        for(int i = 1;i <= n;i ++)
        {
            cin >> h[i];
            f[i] = g[i] = 1;
        }
        int res = 1;
        //我们要找的是基德能够到达每个状态的时候的，通过的最大楼栋数
        for(int i = 1;i <= n;i ++)
        {
            for(int j = 1;j <= i;j ++)
            if(h[i] > h[j])
            {
                f[i] = max(f[j] + 1,f[i]);
                res = max(res, f[i]);
            }
        }//从前往后跳的代码和上面裸题代码相同
        
        for(int i = n;i >= 0;i --)
        {
            for(int j = n;j >= i;j --)
            {
                if(h[j] < h[i])
                {
                    g[i] = max(g[j] + 1, g[i]);
                    res = max(res, g[i]);
                }
            }
        }
        
        cout << res << endl;
    }
    return 0;
}

三、登山

题目链接

圈重点，每次所游历景点的编号都要大于前一个景点，一旦开始下山不再上山了。

显而易见，我们只需要找到i状态前面的最大上升序列，然后加上i之后的最大下降子序列就行，然后取哪一个状态所对应的景点个数最大就行

#include<iostream>
#include<algorithm>
using namespace std;
const int N = 1010;
int n;
int q[N];
int f[N];
int g[N];

int main()
{
    cin >> n;
    for(int i = 1;i <= n;i ++) {
        cin >> q[i];
        f[i] = g[i] = 1;
    }
    int res = 1;
    for(int i = 1;i <= n;i ++)
    {
        for(int j = 1;j <= i;j ++)
        {
            if(q[i] > q[j])
            {
                f[i] = max(f[j] + 1, f[i]);
            }
        }
    }//先从前往后找最大上升子序列，也就是找i状态如果要下山的话，它前面的最大上升子序列是多少
    
    for(int i = n;i >= 1;i --)
    {
        for(int j = n;j >= i;j --)
        {
            if(q[i] > q[j])
            {
                g[i] = max(g[j] + 1, g[i]);
            }
        }
    }//然后找i状态下山的话，的最大下降子序列就行
    
    for(int i = 1;i <= n;i ++)
    {
        res = max(res, f[i] + g[i] - 1);
    }
    
    cout << res;
    return 0;
}

四、合唱队形

题目链接

这个题很显然啊和上面的题目一摸一样，直接找i状态，找到最大的，然后数组减去最多成队列人数的同学就得到最少要剔除的人

#include<iostream>
#include<algorithm>
using namespace std;
const int N = 110;
int q[N];
int f[N];
int g[N];
int n;

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

五、友好城市

题目链接

#include<iostream>
#include<algorithm>
using namespace std;
typedef pair<int,int> PII;
const int N = 5010;
PII q[N];
int f[N];

int main()
{
    int n;
    cin >> n;
    for(int i = 0;i < n;i ++)
    {
        scanf("%d%d", &q[i].first, &q[i].second);
        f[i] = 1;
    }
    
    sort(q,q + n);
    int res = 1;
    for(int i = 0;i < n;i ++)
    {
        for(int j = 0;j <= i;j ++)
        {
            if(q[j].second < q[i].second)
            {
                f[i] = max(f[i], f[j] + 1);
                res = max(f[i], res);
            }
        }
    }
    cout << res;
    return 0;
}

六、最大上升子序列和

题目链接

这里略微变化了一下，我们先找以i状态结尾的上升子序列，然后把每个上升子序列的大小进行取最大，这样就可以得到所有上升子序列的和，然后取最大即可。

#include<iostream>
#include<algorithm>
using namespace std;
const int N = 1010;
int n;
int q[N];
int f[N];

int main()
{
    cin >> n;
    for(int i = 1;i <= n;i ++) 
    {
        cin >> q[i];
        f[i] = q[i];//细节初始化每个i状态等于q[i]
    }
    
    int res = -1e9;
    for(int i = 1;i <= n;i ++)
    {
        for(int j = 1;j <= i;j ++)
        {
            if(q[j] < q[i])
            {
                f[i] = max(f[i], f[j] + q[i]);
            }
            res = max(res, f[i]);
        }
    }
    cout << res;
    return 0;
}