讨论 / 题解!
297285246213 2015-08-28 17:57:50
点我顶贴 收藏 删除
#include<cstdio>

#include<iostream>

using namespace std;

int f[1001];

int tall[1001];

int ans3[1001];

int sht[1001];

int main(){

int n;

cin>>n;

for(int i=1;i<=n;i++)

cin>>tall[i];

f[1]=1;

for(int k=1;k<=n;k++)

{

for(int i=2;i<=k;i++)

{

f[i]=0;

for(int j=1;j<=i;j++)

if(tall[i]>tall[j])

f[i]=max(f[j],f[i]);

f[i]++;

}

int ans=0;

for(int i2=1;i2<=k;i2++)

ans=max(ans,f[i2]);

f[k+1]=1;

for(int i3=k+1+1;i3<=n;i3++)

{

f[i3]=0;

for(int j2=k+1;j2<=i3;j2++)

if(tall[i3]<tall[j2])

f[i3]=max(f[j2],f[i3]);

f[i3]++;

}

int ans2=0;

for(int i4=k+1;i4<=n;i4++)

ans2=max(ans2,f[i4]);

int ans4=n-(ans2+ans);

ans3[k]=ans4;

}

int ans5=999999;

for(int k2=2;k2<=n-1;k2++)

ans5=min(ans5,ans3[k2]);

cout<<ans5;

return 0;

}

查看更多回复
提交回复