首页 > 试题广场 >

合唱队形

[编程题]合唱队形

热度指数：14253 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 64M，其他语言128M
算法知识视频讲解

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

输入描述:

输入的第一行是一个整数N（2 <= N <= 100），表示同学的总数。
第一行有n个整数，用空格分隔，第i个整数Ti（130 <= Ti <= 230）是第i位同学的身高（厘米）。

输出描述:

可能包括多组测试数据，对于每组数据，
输出包括一行，这一行只包含一个整数，就是最少需要几位同学出列。

示例1

输入

8
186 186 150 200 160 130 197 220

输出

算法知识视频讲解

Java

菜鸟葫芦娃

* 思路分析

动态规划求出以每个人结尾的左边和右边的最大队列长度

枚举每个人为“中心点”，计算出满足题目要求的队列长度，记录最大值

我们用left[i]表示从左边起到第i个人结束的最长上升队列的人数，那么得到最优解的结构：left[i] = max{max(left[k] + 1), 1} 0<=k<=i-1 && a[k] < a[i]

同样用right[i]表示从右边起到第i个人结束的最大上升队列的人数，得到：right[i] = max{max(right[k] + 1), 1} i + 1 <= k <= n - 1 && a[k] < a[i]

import java.util.Scanner;
public class Main{

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner in = new Scanner(System.in);
		while (in.hasNextInt()) {
			int cnt = in.nextInt();
			int[] height = new int[cnt];
			for (int i = 0; i < cnt; i++) {
				height[i] = in.nextInt();
			}
			System.out.println(processChorusFormation(height, cnt));
		}
		in.close();
	}

	private static int processChorusFormation(int[] height, int len) {
		// TODO Auto-generated method stub
		int res = 0;
		int[] left = new int[len];
		int[] right = new int[len];
		left[0] = right[len - 1] = 1;
		for (int i = 1; i < len; i++) {
		left[i]=1;
			for (int k =0; k<i; k++) {
				if (height[i] > height[k]) {
					left[i] = Math.max(left[i], left[k] + 1);
				}
			}
		}
		for (int i = len - 2; i >= 0; i--) {
		right[i]=1;
			for (int k = len - 1; k > i; k--) {
				if (height[i] > height[k]) {
					right[i] = Math.max(right[i], right[ k] + 1);
				}
			}
		}
		for (int i = 0; i < len; i++) {
			if (left[i] + right[i] - 1 > res) {
				res = left[i] + right[i] - 1;
			}
		}
		return len-res;
	}

}

编辑于 2016-07-29 09:01:22 回复(0)