DP:合唱团的队形 from斯伦贝谢校招

热乎出炉的斯伦贝谢今年(2015)校招的机试中的一道。online judge模式。内人去笔试，结果虐的体无完肤。好像是3小时5道题。题目并不新感觉比较中正平和，也能充分考察出功底。

题目是老题，没太多可说的。刷刷题，阴郁的心情能好一点。

题目：
N位同学站成一排，音乐老师要请其中的(N-K)位同学出列，使 得剩下的K位同学排成合唱队形。   合唱队形是指这样的一种队形：设K位同学从左到右依次编号为1，2…，K，他们的身高分别为T1，T2，…，TK，  则他们的身高满足T1<...Ti+1>…>TK(1<=i<=K)。   你的任务是，已知所有N位同学的身高，计算最少需要几位同学出列，可以使得剩下的同学排成合唱队形。

解析:
1. 对于解: T1<...Ti+1>…>TK 来说， Ti左边（包括Ti)为递增序列，Ti右边为递减序列
2. 设函数f(x) 为 T0~ Tx这个序列中 包含x的最长递增子序列
3. 设函数g(x) 为 Tx~T(n-1)这个序列中 包含x的最长递减子序列
4. 根据以上假设，对于x 包含x的最长的，符合条件的合唱团序列 h(x) = f(x) + g(x) -1
5. 最终，需要去除的最少人的个数为K = N - max(h(x)) x∈(0,N-1)

a. 对于函数f(x),有
f(x) = max( f(i)) + 1  其中i∈（0，x-1) 且Ti 伪代码：
  f(x) = 0;
  for  i  in ( 0 .. x-1){
         if ( Ti< Tx and  and f(x)                f(x) = f(i);
         }
  }
  f(x) +=1;


b.对于函数g(x), 偷懒的办法就是可以把输入倒过来，用f(x)算一遍，然后将结果倒过来就好了。
当然，两次翻转会增加O(n)的复杂度。你也可以选择把f(x)的条件倒过来。

c.如果说我们需要输出最后的结果序列，我们就需要额外的空间来存储每步的结果。
对于f(x) ，我们返回两个值  f(x) = maxlen, prev
maxlen为包含Tx的最长递增子序列的长度
prev为包含Tx的最长递增子序列中Tx的前一个元素
类似链表的结构，最后可以方便的输出结果。
（示例代码中未实现该部分）


下面的代码中，采取了折衷的方法，将输入倒了过来，只不过最后求最大值的时候用对len取补的方法处理了下标。

#include <stdio.h>
#include <stdlib.h>
void fun(int *input, int size, int* result){
    result[0] = 1;
    int i;
    for(i = 1; i<size; i++){
         int j = 0;
         int tmax = 0;
         for(;j<i;j++){
             if(input[j]<input[i] && tmax < result[j]){
                 tmax = result[j];
             }
             result[i] = tmax + 1;
         }
    }
}

void rev(int* input , int size){
   int start = 0;
   int end = size -1;
   while( start<end){
        int tmp = input[start];
        input[start] = input[end];
        input[end] = tmp;
        start ++;
        end --;
   }
}

int main(){
int input[] = {1,2, 5, 1,2, 3};
int len = sizeof(input)/sizeof(int);

int left[len];
int right[len];
fun(input, len , left);
rev(input,len);
fun(input, len , right);
int max = 0;
int i;
for(i = 0; i<len; i++){
   //printf("num=%d : left(%d) = right(%d)\n", input[len-i-1],left[i],right[len-i-1]);
   if (max< left[i] + right[len-i-1] - 1)
       max = left[i] + right[len-i-1] -1 ;
}
printf("%d\n", len - max);
}