NOIP2004 提高組 NOIP2004 3.合唱隊型
作法:(DP)LIS+暴力
/*************************************************/
#include<stdio.h>
#include<stdlib.h>
int people[101]={0};
int array[101]={0};
int LIS(int n,int cut)
{
int i,j;
for(i=0;i<cut;i++) array[i]=1;
for(i=0;i<cut;i++)
for(j=i+1;j<cut;j++)
if(people[j]>people[i])
array[j]=(array[j]>array[i]+1)?array[j]:array[i]+1;
int ans=0;
for(i=0;i<cut;i++)
ans=(ans>array[i])?ans:array[i];
for(i=cut;i<n;i++) array[i]=1;
for(i=cut;i<n;i++)
for(j=i+1;j<n;j++)
if(people[j]<people[i])
array[j]=(array[j]>array[i]+1)?array[j]:array[i]+1;
int max=0;
for(i=cut;i<n;i++)
max=(max>array[i])?max:array[i];
return max+ans;
}
main()
{
int n,a,b,c,ans=0;
scanf("%d",&n);
for(a=0;a<n;a++)
scanf("%d",&people[a]);
for(a=0;a<n;a++)
{
int temp=LIS(n,a);
ans=(ans>temp)?ans:temp;
}
printf("%d\n",n-ans);
return 0;
}