2009-06-28 19:07:45來源不明

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;  
}