翻到半年前写的代码,感觉又懂了,胡一下吧

线性dp

  • 对于每个点,看看这个点向前最高,向后最矮,就是这个点可以形成的最大合唱队列

原数据:186 186 150 200 160 130 197 220

离散一下:4 4 2 6 3 1 5 7

就是这个亚子

1号点最长队形为:4 2 1

2号点最长队形为:4 2 1

3号点最长队形为:2 1

4号点最长队形为:4 6 3 1

5号点最长队形为:2 3 1

6号点最长队形为:1

7号点最长队形为:2 3 5

8号点最长队形为:2 3 5 7

相当于把每个点当作合唱队形里最高的那个,看以这个点向前或向后可以有多长,最长的就有最少的出队人数

由于一定

所以就是求最长上升和最长下降(严格递减,递增)

  • 最长上升
for(int i=1;i<=n;i++){
        f[i]=1;
        for(int j=1;j<i;j++)
            if(h[i]>h[j])
                f[i]=max(f[i],f[j]+1);
    }

可以把 f[ ] 理解成 dp 数组

每到一个点,去找这个点前面比小的数,比较当前最长序列与i+找到数的最长序列取最大

下降同礼

贴个码

#include<bits/stdc++.h>
using namespace std;
const int M=1e2+110;;
int read(){
	int sum=0,k=1;
	char c=getchar();
	while(c>'9'||c<'0'){
		if(c=='-') k=-1;
		c=getchar();
	}while(c>='0'&&c<='9'){
		sum=sum*10+c-48;
		c=getchar();
	}return sum*k;
}
int f[M],g[M],h[M];
int main(){
    int n=read(),ans=0;
    for(int i=1;i<=n;i++)h[i]=read();
    for(int i=1;i<=n;i++){
        f[i]=1;
        for(int j=1;j<i;j++)
            if(h[i]>h[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(h[i]>h[j])
                g[i]=max(g[i],g[j]+1);
    }
    for(int i=1;i<=n;i++)
        ans=max(ans,f[i]+g[i]-1);
    cout<<n-ans<< endl;
    return 0;
}