题目地址:http://xcacm.hfut.edu.cn/problem.php?id=1010

题目描述

宣城校区要举行一年一度的广播操比赛,13级计算机某班N位同学站成一排, 辅导员要请其中的(N-K)位同学出列,使得剩下的K位同学排成广播操队形。广播操队形是指这样的一种队形:设K位同学从左到右依次编号为1,2…,K,他们的身高分别为T1,T2,…,TK, 则他们的身高满足:

$$T_1<\dots <="" t_i="">T_{i+1}>\dots >T_K(1\leq i\leq K)$$

你的任务是,已知所有N位同学的身高,计算最少需要几位同学出列,可以使得剩下的同学排成广播操队形。

思路

这是一个动态规划问题,双向最长递增子序列。按身高求出从左到右的递增子序列长度,再求出从右到左的递增子序列长度。然后合并求出最大的K,即出队人数为N-K。

AC代码

/*************************************************************************
    > File Name: 1010.cpp
      > Author: Netcan
      > Blog: http://www.netcan.xyz
      > Mail: 1469709759@qq.com
      > Created Time: Mon 04 May 2015 11:27:11 CST
 ************************************************************************/

#include <iostream>
#include <vector>
#include <string>
#include <queue>
#include <algorithm>
#include <cmath>
#include <ctime>
#include <cstdio>
#include <sstream>
#include <deque>
#include <functional>
#include <iterator>
#include <list>
#include <map>
#include <memory>
#include <stack>
#include <set>
#include <numeric>
#include <utility>
#include <cstring>
using namespace std;

int main()
{
    int N; // 人数
    int h[105]; //身高值 
    int h1[105]; // 从左往右的最长递增子序列
    int h2[105]; // 从右往左的最长递增子序列
    while(scanf("%d", &N) == 1) { 
        for(int i=0; i<N; ++i)
            scanf("%d", &h[i]); 
        for(int i=0; i<N; ++i) { // 求h1
            h1[i] = 1;
            for(int j=0; j<i; ++j)
                if(h[i]>h[j]) h1[i] = max(h1[i], h1[j]+1);
        }
        for(int i=N-1; i>=0; --i) { // 求h2
            h2[i] = 1;
            for(int j=N-1; j>i; --j)
                if(h[i] > h[j]) h2[i] = max(h2[i], h2[j]+1);
        }
        int K=0;
        for(int i=0;i<N; ++i) // 求广播体操队形最大人数K
            K = max(K, h1[i]+h2[i]-1); // -1,减去重叠的一个人。
        printf("%d\n", N-K);
    }
    return 0;
}