学步园

HWOJ 合唱队

题目：合唱队

样例输入：
8
186 186 150 200 160 130 197 200
样例输出：
4
题目分析：
算法思路：
①动态规划求出以每个人结尾的左边和右边的最大队列长度
②枚举每个人为“中心点”，计算出满足题目要求的队列长度，记录最大值
③用left[i]表示从左边起到第i个人结束的最长上升队列的人数，那么得到最优解的结构：left[i]，用right[i]表示从右边起到第i个人结束的最大上升队列的人数，得到：right[i]
④初始化left[i] = 1通过内循环更新lefe[i]，right[i]也一样
⑤最后循环求出最大的合唱队列
⑥循环 第一个左边：i = 1 i < n j = 0 j < i 右边 i = n-2 i >=0 j = n-1 j > i
学习笔记：
学会动态分析，找出最优解

===============================================================================
参考代码：

//合唱对.c
//2014.7.5
#include <stdio.h>
#include <string.h>
#define maxn 100+5

//a[i]表示第i个人的身高，left[i]表示从左边第一个到a[i]个最长上升序列，right[i]表示从右边第一个到a[i]的最长上升子序列
int a[maxn];
int left[maxn];  
int right[maxn];

int main()
{
    int i,j,n,max,cnt = 0;
    while(scanf("%d",&n) != EOF)
    {
        for(i = 0; i < n;i++)
        {
            scanf("%d",&a[i]);
        }

        //初始化全部设为0
        memset(left, 0, sizeof(left));
        memset(right, 0, sizeof(right));

        //左侧的最长上升子序列
        left[0] = 1;
        for(i = 1;i < n; i++)
        {
            left[i] = 1;
            for(j =0; j<i ;j++)
            {
                if(a[i] > a[j] && left[i] < left[j] + 1)
                    left[i] = left[j] + 1;
            }
        }

        //右侧最长上升子序列
        right[n-1] = 1;
        for(i = n-2; i >= 0; i--)
        {
            right[i] = 1;
            for(j = n-1;j > i;j--)
            {
                if(a[i] > a[j] && right[i] < right[j] + 1)
                {
                    right[i] = right[j] + 1;
                }
            }
        }

        for(i = 0; i < n; i++)
        {
            if(left[i] + right[i] - 1 > cnt)
                cnt = left[i] + right[i] - 1;
        }

        printf("%d\n",n - cnt);
    }

    return 0;
}