LIS问题（最长上升子序列问题）

最长上升子序列题目链接

895. 最长上升子序列 - AcWing题库

最长上升子序列代码

#include<iostream>
#include<algorithm>

using namespace std;
const int N = 1010;
int n;
int a[N], f[N];

int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;++i)
        scanf("%d",&a[i]);
    for(int i=1;i<=n;i++)
    {
        f[i]=1;
        for(int j=1;j<i;j++){
            if(a[j]<a[i]){
                f[i] = max(f[i], f[j]+1);
            }
        }
    }
    int res = 0;
    for(int i=1;i<=n;++i){
        res = max(res,f[i]);
    }
    printf("%d\n",res);
    return 0;
}

怪盗基德的滑翔翼题目链接

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

怪盗基德的滑翔翼代码

#include<iostream>
#include<algorithm>
using namespace std;

const int N =110;
int n;
int a[N], f[N];

int main(){
    int T;
    scanf("%d",&T);
    while(T--){
        scanf("%d",&n);
        for(int i=1;i<=n;++i){
            scanf("%d",&a[i]);
        }
           int res=0;
        for(int i=1;i<=n;++i){
            f[i]=1;
            for(int j=1;j<=i;++j){
                if(a[i]>a[j]){
                    f[i]=max(f[i],f[j]+1);
                }
            }
            res = max(res, f[i]);
        }
        for(int i=1;i<=n;++i){
            f[i]=1;
            for(int j=1;j<=i;++j){
                if(a[i]<a[j]){
                    f[i]=max(f[i],f[j]+1);
                }
            }
            res = max(res, f[i]);
        }
        printf("%d\n",res);
    }
    return 0;
}

登山题目链接

1014. 登山 - AcWing题库

登山代码

#include<iostream>
#include<algorithm>
using namespace std;

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

int main(){
        scanf("%d",&n);
        for(int i=1;i<=n;++i){
            scanf("%d",&a[i]);
        }
           int res=0;
        for(int i=1;i<=n;++i){
            f[i]=1;
            for(int j=1;j<=i;++j){
                if(a[i]>a[j]){
                    f[i]=max(f[i],f[j]+1);
                }
            }
        }
        for(int i=n;i>=1;--i){
            g[i]=1;
            for(int j=n;j>=i;--j){
                if(a[i]>a[j]){
                    g[i]=max(g[i],g[j]+1);
                }
            }
        }
        for(int i=1;i<=n;++i){
            res = max(res,f[i]+g[i]-1);
        }
        printf("%d\n",res);
    return 0;
}

合唱队形题目链接

482. 合唱队形 - AcWing题库

合唱队形代码

#include<iostream>
#include<algorithm>
using namespace std;

const int N =110;
int n;
int a[N], f[N], g[N];

int main(){
        scanf("%d",&n);
        for(int i=1;i<=n;++i){
            scanf("%d",&a[i]);
        }
           int res=0;
        for(int i=1;i<=n;++i){
            f[i]=1;
            for(int j=1;j<=i;++j){
                if(a[i]>a[j]){
                    f[i]=max(f[i],f[j]+1);
                }
            }
        }
        for(int i=n;i>=1;--i){
            g[i]=1;
            for(int j=n;j>=i;--j){
                if(a[i]>a[j]){
                    g[i]=max(g[i],g[j]+1);
                }
            }
        }
        for(int i=1;i<=n;++i){
            res = max(res,f[i]+g[i]-1);
        }
        printf("%d\n",n-res);
    return 0;
}

友好城市题目链接

1012. 友好城市 - AcWing题库

友好城市代码

#include<iostream>
#include<algorithm>

using namespace std;

typedef pair<int, int> PII;

const int N = 5010;

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

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

最大上升子序列和题目链接

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

最大上升子序列和代码

#include<iostream>
#include<algorithm>

using namespace std;
const int N = 1010;
int n;
int a[N], f[N];

int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;++i)
        scanf("%d",&a[i]);
    for(int i=1;i<=n;i++)
    {
        f[i]=a[i];
        for(int j=1;j<i;j++){
            if(a[j]<a[i]){
                f[i] = max(f[i], f[j]+a[i]);
            }
        }
    }
    int res = 0;
    for(int i=1;i<=n;++i){
        res = max(res,f[i]);
    }
    printf("%d\n",res);
    return 0;
}