本题有DP O(n^2)和贪心(nlogn)的两种解法
DP的写法是模板,更好写,需要熟练背诵
#include<bits/stdc++.h>
using namespace std;
const int N = 110;
int f[N],g[N],h[N];
int n;
int main()
{
cin>>n;
for(int i=1;i<=n;i++) cin>>h[i];
for(int i=1;i<=n;i++)
{
f[i]=1;
for(int j=1;j<i;j++)
{
if(h[j]<h[i])
{
f[i]=max(f[i],f[j]+1);
}
}
}
for(int i=n;i;i--)
{
g[i]=1;
for(int j=n;j>i;j--)
{
if(h[j]<h[i])
{
g[i]=max(g[i],g[j]+1);
}
}
}
int res=0;
for(int i=1;i<=n;i++)
{
res = max(res,f[i]+g[i]-1);
}
cout<<n-res;
}
本题需要注意的点在于逆向LIS的实现
注意g[i]表示的含义是以i结束的逆向递增序列的最长个数
Code:
for(int i=n;i;i--)
{
g[i]=1;
for(int j=n;j>i;j--)
{
if(h[j]<h[i])
{
g[i]=max(g[i],g[j]+1);
}
}
}
i是靠内的,j是i右边靠外的