合唱队形.txt

ACM一道合唱队形排列问题

#include <fstream> 
#include <cstring> 
using namespace std; 

ifstream fin("chorus.in"); 
ofstream fout("chorus.out"); 

const int maxn = 100; 

int n, a[maxn]; 
int incsq[maxn], decsq[maxn]; 

void init() { 
fin >> n; 
for (int i = 0; i < n; i ++) 
fin >> a[i]; 
} 

void LIncSeq() 
{ 
int i, low, high, mid, ans = 0; 
int sol[maxn]; 

for (i = 0; i < n; i ++) { 
low = 1; high = ans; 
while (low <= high) { 
mid = (low + high) >> 1; 
if (sol[mid] < a[i]) low = mid + 1; 
else high = mid - 1; 
} 
if (low > ans) ans ++; 
sol[low] = a[i]; 
incsq[i] = ans; 
} 
} 

void LDecSeq() 
{ 
int i, low, high, mid, ans = 0; 
int sol[maxn]; 

for (i = 0; i < n; i ++) { 
low = 1; high = ans; 
while (low <= high) { 
mid = (low + high) >> 1; 
if (sol[mid] > a[i]) low = mid + 1; 
else high = mid - 1; 
} 
if (low > ans) ans ++; 
sol[low] = a[i]; 
decsq[i] = ans; 
} 
} 

void work() { 
int i, max = 0; 

LIncSeq(); 
LDecSeq(); 

for (i = 0; i < n; i ++) 
if (incsq[i] + decsq[i] - 1 > max) 
max = incsq[i] + decsq[i] - 1; 

fout << n - max << endl; 
} 

int main() { 
init(); 
work(); 
return 0; 
} 








#include <stdio.h>

#include <string.h>

#define MAXN 200

int main()

{

       int n, a[MAXN], b[MAXN], c[MAXN], i, j, max;

       scanf("%d", &n);

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

              scanf("%d", &a[i]);

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

       }

       printf("%d\n", n - max + 1);

       return 0;

}