The longest ascending subsequence model acwing 482 Chorus formation

Longest ascending subsequence model AcWing 482. Chorus formation

Original link

AcWing 482. Chorus formation

Algorithm tags

DP linear DP Longest ascending subsequence

Ideas

Ask for i Ending ascending sequence , With i The reverse rising at the end is the descending sequence , Get to i It is a sequence in which the dividing point rises first and then falls , Taking the maximum , Reduce the total by the maximum .

Code

#include<bits/stdc++.h>
#define int long long
#define rep(i, a, b) for(int i=a;i<b;++i)
#define Rep(i, a, b) for(int i=a;i>=b;--i)
using namespace std;
const int N = 1005, INF = 0x3f3f3f3f;
int f[N], f1[N], a[N];
inline int read(){
   int s=0,w=1;
   char ch=getchar();
   while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
   while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
   return s*w;
}
void put(int x) {
    if(x<0) putchar('-'),x=-x;
    if(x>=10) put(x/10);
    putchar(x%10^48);
}
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int n=read();
	rep(i, 1, n+1){
	    a[i]=read();
	}
	int ans=0, ans1=0, ans2=0;
	//  With i Ending ascending sequence 
	rep(i, 1, n+1){
	    f[i]=1;
	    rep(j, 1, i){
	        if(a[j]<a[i]){
	            f[i]=max(f[i], f[j]+1);
	        }
	    }
	    ans1=max(ans1, f[i]);
	}
	//  With i The reverse rising at the end is the descending sequence 
	Rep(i, n, 0){
	    f1[i]=1;
	    Rep(j, n, i+1){
	        if(a[j]<a[i]){
	            f1[i]=max(f1[i], f1[j]+1);
	        }
	    }
	    ans2=max(ans2, f1[i]);
	}
	//  Go up first   Post descent sequence 
	rep(i, 1, n+1){
	    ans=max(ans, (f[i]+f1[i]-1));
	}
	printf("%lld\n", n-ans);
}

And y The general code is consistent

y Master code

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 1010;

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

int main()
{
    scanf("%d", &n);
    for (int i = 0; i < n; i ++ ) scanf("%d", &h[i]);

    for (int i = 0; i < n; i ++ )
    {
        f[i] = 1;
        for (int j = 0; j < i; j ++ )
            if (h[i] > h[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 (h[i] > h[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);

    printf("%d\n", n - res);

    return 0;
}

Originality is not easy.
Reprint please indicate the source
If it helps you Don't forget to praise and support