最长上升子序列的变形(简单dp)
思路
刚刚入门dp,学的不是很好所以没有想到o.o!
只需要正着求着一遍最长上升子序列f1[n],然后倒着求一遍最长上升子序列f2[n] (相当于正着的最长下降子序列),然后找到序列中的一个点i,这个点i使得f1[i]+f2[i]-1最大(为啥要减一呢,因为i这个点被统计了两次),所以ans=n-(f1[i]+f2[i]-1)最小.
代码
#include<bits/stdc++.h>
using namespace std;
const int N=1e2+10;
int n,f1[N],f2[N];
int main()
{
cin>>n;
vector<int> v(n);
for(int i=0;i<n;i++)
{
f1[i]=1;
f2[i]=1;
}
for(int i=0;i<n;i++)
{
int x;
cin>>x;
v[i]=x;
}
for(int i=1;i<n;i++)
for(int j=0;j<i;j++)
{
if(v[i]>v[j])
f1[i]=max(f1[i],f1[j]+1);
}
reverse(v.begin(),v.end());
for(int i=1;i<n;i++)
for(int j=0;j<i;j++)
{
if(v[i]>v[j])
f2[i]=max(f2[i],f2[j]+1);
}
int length=INT_MIN;
for(int i=0;i<n;i++)
length=max(length,f2[n-1-i]+f1[i]-1);
cout<<n-length<<endl;
return 0;
}