首页 > 试题广场 >

合唱队形

[编程题]合唱队形

热度指数：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

输出

算法知识视频讲解

鱼儿恋上水

发表于 2020-05-19 23:15:54

思路：动态规划：正反两次运用LIS求出以每一个点结尾的从前往后最长递增子序列以每一个结点结尾的从后往前最长递增子序列当最大时，记作，表示剩下的同学排成合唱队形最多的人数则有为当前状态下最少需要出列的同学人数（因为i这个位置被重复计算了一次，故需要+1）代码： /* LIS最长递增子序列展开全文

健康快乐最重要

发表于 2020-02-29 12:42:32

相当于求两个最长递增子序列吧。emmm，还没看大佬写的，暂且是这么个想法。 dp1[i]表示以a1[i]结尾的最长递增子序列然后把a1[i]转置成a2[i]，接着求以a2[i]为结尾的最长递增子序列dp2[i]，(相当于求以a[i]为结尾的左边正序一个最长递增，后边倒序的一个最长递减)。然后对展开全文

牛客440904392号

发表于 2024-09-29 21:42:44

import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n 展开全文

在考古的小鱼干很有气魄

发表于 2023-03-10 10:03:24

#include <bits/stdc++.h> #define MAX 100 using namespace std; int main() { int dp1[MAX], dp2[MAX], data[MAX], i, j, ans; int n; cin 展开全文

牛客166649559号

发表于 2024-03-22 21:36:49

#include<iostream> #include<algorithm> using namespace std; int n,maxsum=0; int sum[100]; void fun(int a[],int flag){ int dp[100]={1}; f 展开全文

牛客995515196号

发表于 2023-02-06 16:10:02

#include <stdio.h> void fun_up(int *stu,int i,int n,int *up) { int max=1; for(int j=0;j<i;j++) { if(up[ 展开全文

loveC--

发表于 2024-03-18 17:00:47

#include<iostream> using namespace std; #define N 105 int arr[N]; //从左往右的最大递增子序列 int dp1[N]; //从右往左的最大递增子序列 int dp2[N]; int main() { in 展开全文

程昱同学

发表于 2023-01-23 16:52:36

#include <bits/stdc++.h> using namespace std; vector<int>h; int n; int long_up(int l,int r) { int maxl=1; int dp[100]; for(int 展开全文

lyw菌

发表于 2023-03-10 19:10:59

#include "stdio.h" #include "climits" using namespace std; int n;//学生人数 int student[110];// 存储学生身高 int leftDP[110];//存储从左到右的最长上升子序列长度 int rightDP[110 展开全文