牛客网之华为机试题：HJ24 合唱队（动态规划）
一. 简介
本文记录牛客网上华为机试题：合唱队
本文通过动态规划思路，以C语言实现。
二. 牛客网之华为机试题：HJ24 合唱队（动态规划）
描述
音乐课上，老师将 nn 位同学排成一排。老师希望在不改变同学相对位置的前提下，从队伍中选出最少数量的同学，使得剩下的同学排成合唱队形。
你能帮助老师计算，最少需要出列多少位同学，才能使得剩下的同学排成合唱队形？
输入描述：
第一行输入一个整数 n(1≦n≦3000)代表同学数量。
第二行输入 n 个整数 h1,h2,…,hn(0≦hi≦105)代表每一位同学的身高。
输出描述：
输出一个整数，代表最少需要出列的同学数量。
示例1
输入：8
186 186 150 200 160 130 197 200
输出：4
说明：
在这个样例中，有且仅有两种出列方式，剩下的同学分别为 {186,200,160,130}{186,200,160,130} 和 {150,200,160,130}{150,200,160,130} 。
解题思路：动态规划
1.求每个位置左侧最长递增子序列（从左到右）
2. 求每个位置上右侧最长递减子序列（从右向左）
3.统计最长子序列（即最长合唱队形）
4. 最少出列人数：总人数-最长子序列数
C语言实现如下：
/*
动态规划
*/
#include <stdio.h>
#include <stdlib.h>int main() {int n = 0;int* height;int i, j;int max_len = 0;if(scanf("%d", &n) != EOF) {height = (int*)malloc(n*sizeof(int));for(i=0; i<n; i++) {scanf("%d", &height[i]);}}//1.求每个位置左侧最长递增子序列（从左到右）int* left_dp = (int*)malloc(n*sizeof(int));for(i=0; i<n; i++) {left_dp[i] = 1; //每个元素自身就是1个子序列for(j=0; j<i; j++) {//(left_dp[j]+1)>left_dp[i]://把height[i]接在以height[j]结尾的递增序列后面，能形成比当前记录更长的序列//那么就更新dp_inc[i]if((height[j]<height[i]) && ((left_dp[j]+1)>left_dp[i])) {left_dp[i]=left_dp[j]+1;}}}//2. 求每个位置上右侧最长递减子序列（从右向左）int* right_dp = (int*)malloc(n*sizeof(int));for(i=n-1; i>=0; i--) {right_dp[i]=1;for(j=n-1; j>i; j--) {//(right_dp[i]+1)>right_dp[i]://把height[i]接在以height[j]结尾的递增序列前面，能形成比当前记录更长的序列//则更新 right_dp[i]if((height[j]<height[i]) && ((right_dp[j]+1)>right_dp[i])) {right_dp[i]=right_dp[j]+1;}}}//3.统计最长子序列（即最长合唱队形）//上面两种子序列数目相加，求最长子序列数目for(i=0; i<n; i++) {if((left_dp[i]+right_dp[i]-1) > max_len) {max_len = left_dp[i]+right_dp[i]-1;}}//4. 最少出列人数：总人数-最长子序列数printf("%d\n", (n-max_len));free(height);height=NULL;free(left_dp);left_dp=NULL;free(right_dp);right_dp=NULL;return 0;
}