合唱队.c

算法分析ACM题目：合唱队型算法 保证能运行！算法分析课程必备！

#include <stdio.h>

#include <string.h>

#define MAXN 200
int he(int n,int a[])
{
	int b[MAXN], c[MAXN],  i, j, max;  
	memset(b, 0, sizeof(a));

       memset(c, 0, sizeof(c));

       b[1] = 1;

       for (i = 2; i <= n; i++)

       {

              max = 0;

              for (j = i - 1; j >= 1; j--)

              {

                     if (a[j] < a[i] && b[j] + 1 > max)

                            max = b[j];

              }

              b[i] = max + 1;

       }

       c[n] = 1;

       for (i = n - 1; i > 0; i--)

       {

              max = 0;

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

              {

                     if (a[j] < a[i] && c[j] + 1 > max)

                            max = c[j];

              }

              c[i] = max + 1;

       }

       max = b[1] + c[1];

       for (i = 2; i <= n; i++)

       {

              if (b[i] + c[i] > max)

                     max = b[i] + c[i];

       }

       return n - max + 1;

}
int main()

{
	

	int n, a[MAXN],i,j,min[MAXN];
	   for(j=0;;j++)
	   {

       scanf("%d", &n);
	   if(n==0)
		   break;

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

              scanf("%d", &a[i]);
	   min[j]=he(n,a);
	   }
	   for(i=0;i<j;i++)
		printf("%d\n",min[i]);
     
       return 0;

}