题目描述

怪盗基德滑翔翼

说明

最长上升子序列类问题，枚举倒数第二个数的状态，j从1到i-1；

#include <iostream>
#include <cstring>
using namespace std;
const int N=120;

int a[N];
int f[N];
int df[N];

int main()
{
    int n;
    cin>>n;

    while(n--)
    {
        int m;
        memset(f,0,sizeof f);
        memset(df,0,sizeof df);
        memset(a,0,sizeof a);
        cin>>m;
        int cnt=0;
        for(int i=1;i<=m;i++)
        {
            cin>>a[i];
        }
        for(int i=1;i<=m;i++)
        {
            f[i]=1;
            for(int j=1;j<=i-1;j++)
            {
                if(a[j]>a[i])
                {
                    f[i]=max(f[i],f[j]+1);
                }
            }
        }
        for(int i=m;i>=1;i--)
        {
            df[i]=1;
            for(int j=m;j>=i+1;j--)
            {
                if(a[j]>a[i])
                {
                    df[i]=max(df[i],df[j]+1);
                }
            }
        }

        int res=0;
        for(int i=1;i<=m;i++)
        res=max(res,f[i]);

        int res2=0;
        for(int i=m;i>=1;i--)
        res2=max(res2,df[i]);

        res=max(res,res2);
        cout<<res<<endl;

    }
}

2023/11/23

最大上升子序列，正着反着各做一遍

#include <iostream>
#include <cstring>

using namespace std;

const int N = 1010;
int n,m;
int f[N], a[N];

int main()
{
    cin>>m;
    while(m--)
    {
        memset(f,0,sizeof(f));
        memset(a,0,sizeof(a));
        cin>>n;
        for(int i=1;i<=n;i++)
        {
            cin>>a[i];
        }

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


        int res1=0;
        for(int i=1;i<=n;i++)
        {
            res1 = max(res1, f[i]);
        }

        memset(f,0,sizeof(f));

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


        int res2=0;
        for(int i=1;i<=n;i++)
        {
            res2 = max(res2, f[i]);
        }

        cout<<max(res1, res2)<<endl;
    }

    return 0;
}