摸索C語言 前身 : 摸索C語言 http://mypaper.pchome.com.tw/iustlovefish 現在即將就讀中興大學資訊科學與工程學系 XD

79愛的鼓勵 1訂閱站台

作法:(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;  
}