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

拦截导弹题目链接

1010. 拦截导弹 - AcWing题库

拦截导弹代码

#include<iostream>
#include<algorithm>

using namespace std;
const int N = 1010;
int n,res;
int a[N], f[N], g[N];
// g[N]:存储当前所有已经开好的子序列的结尾的数
int main(){
    while(cin>>a[++n]);
    res = 0;
    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);
            }
        }
        res = max(res,f[i]);
    }
    cout << res <<endl;
    int cnt = 0;
    for(int i=1;i<=n;++i){
        int k = 0;
        while(k<cnt&&g[k]<a[i]) k++; 
        g[k]=a[i];
        if(k>=cnt)
            cnt++;
        
    }
    printf("%d\n",cnt);
    return 0;
}

导弹防御系统题目链接

187. 导弹防御系统 - AcWing题库

导弹防御系统代码

#include<iostream>
#include<algorithm>

using namespace std;
const int N = 55;
int n;
int q[N];
int up[N],down[N];
int ans;

void dfs(int u, int su, int sd)
{
    if (su + sd >= ans) return;
    if(u == n)
    {
        ans = su + sd;
        return ;
    }
    int k = 0;
    while(k<su && up[k]>=q[u]) k++;
    int t = up[k];
    up[k] = q[u];
    if(k<su) dfs(u+1, su, sd);
    else dfs(u+1, su+1, sd);
    up[k] = t;
    
    k = 0;
    while(k<sd && down[k]<=q[u]) k++;
    t = down[k];
    down[k] = q[u];
    if(k<sd) dfs(u+1, su, sd);
    else dfs(u+1, su, sd+1);
    down[k] = t;
}
int main(){
    while(cin>>n,n)
    {
        for(int i=0;i<n;++i) cin>>q[i];
        ans = n;
        dfs(0, 0, 0);
        cout<<ans<<endl;
    }
    return 0;
} 

最长公共上升子序列题目链接

272. 最长公共上升子序列 - AcWing题库

最长公共上升子序列系统代码

#include<iostream>
#include<algorithm>

using namespace std;
const int N = 3010;

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

int main(){
    scanf("%d", &n);
    for(int i=1;i<=n;++i) scanf("%d", &a[i]);
    for(int i=1;i<=n;++i) scanf("%d", &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(b[j]<a[i])
            {
                maxv = max(maxv, f[i-1][j]+1);
            }
        }
    }
    int res=0;
    for(int i=1;i<=n;++i){
        res = max(res, f[n][i]);
    }
    printf("%d\n", res);
    return 0;
}