首页 > 试题广场 >

合唱队

[编程题]合唱队
  • 热度指数：342430 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 32M，其他语言64M
  • 算法知识视频讲解
\hspace{15pt}音乐课上，老师将 n 位同学排成一排。老师希望在不改变同学相对位置的前提下，从队伍中选出最少数量的同学，使得剩下的同学排成合唱队形。
\hspace{15pt}记合唱队形中一共有 k 位同学，记编号为 1,2,\dots,k ，第 i 个人的身高为 h_i 。要求：存在一位同学编号为 i \left(1 < i < k\right) ，使得 h_1,h_2,\dots,h_{i-1} 严格递增，且 h_{i+1},h_{i+2},\dots,h_k 严格递减；更具体地，合唱队形呈 h_1 < h_2 < \cdots < h_{i-1} < h_i 、h_i > h_{i+1} > \cdots > h_k 。
\hspace{15pt}你能帮助老师计算，最少需要出列多少位同学，才能使得剩下的同学排成合唱队形？

输入描述:
\hspace{15pt}第一行输入一个整数 n \left(1 \leqq n \leqq 3000\right) 代表同学数量。
\hspace{15pt}第二行输入 n 个整数 h_1,h_2,\dots,h_n \left(0 \leqq h_i \leqq 10^5\right) 代表每一位同学的身高。


输出描述:
\hspace{15pt}输出一个整数，代表最少需要出列的同学数量。
示例1

输入

8
186 186 150 200 160 130 197 200

输出

4

说明

\hspace{15pt}在这个样例中，有且仅有两种出列方式，剩下的同学分别为 \{186, 200, 160, 130\} 和 \{150, 200, 160, 130\} 。
算法知识视频讲解
添加回答
Java
牛客最小的小白头像 牛客最小的小白 
import java.util.*;

public class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        while(sc.hasNext()){
            //处理输入
            int n = sc.nextInt();
            int[] height = new int[n];
            for(int i=0; i<n; i++){
                height[i] = sc.nextInt();
            }
            //每个位置左侧最长上升子序列
            int[] numL = new int[n];
            for(int i=0; i<n; i++){
                for(int j=0; j<i; j++){//左侧比height[i]小的位置最长上升序列长度
                    if(height[i]>height[j]) numL[i] = Math.max(numL[i], numL[j]);
                }
                numL[i] += 1;//左侧比height[i]小位置最长上升序列长度+1
            }
            //每个位置右侧最长下降子序列
            int[] numR = new int[n];
            for(int i=n-1; i>=0; i--){
                for(int j=n-1; j>i; j--){//右侧比heigth[i]小的位置最长下降序列长度
                    if(height[i]>height[j]) numR[i] = Math.max(numR[i], numR[j]);
                }
                numR[i] += 1;//右侧比height[i]小位置最长下降序列长度+1
            }
            //根据每个位置最长合唱队numL[i]+numR[i]-1，求出所有位置中最大值
            int maxLen=0;
            for(int i=0; i<n; i++){
                if(numL[i]+numR[i]-1>maxLen) maxLen = numL[i]+numR[i]-1;
            }
            //最后n-maxLen即为需要出列人数
            System.out.println(n-maxLen);
        }
    }
}

发表于 2021-08-20 14:39:32 回复(0)
Hunter&Liu头像 Hunter&Liu
javaScript 解决方案，多多指教 
while(line = readline()) {
    let arrL = [1];
    let arrR = [];
    arrR[line-1] = 1;
    let groupArr = [];
    let max = 1;
    let heightArr = readline().split(" ");
    line = parseInt(line);
    for(let i in heightArr) {
        heightArr[i] = parseInt(heightArr[i]);
    }
    
    // left
    for(let m = 0; m<line; m++) {
        arrL[m] = 1;
        for(let n = 0; n<m; n++) {
            if(heightArr[m] > heightArr[n]){
                arrL[m] = arrL[m]>(arrL[n]+1)? arrL[m]:(arrL[n]+1);
            }
        }
    }
    // right
    for(let m = line-1; m>=0; m--) {
        arrR[m] = 1;
        for(let n = line-1; n>m; n--) {
            if(heightArr[m] > heightArr[n]){
                arrR[m] = (arrR[n]+1)>arrR[m]? (arrR[n]+1): arrR[m];
            }
        }
    }

    // All
    for(let m = 0; m< line; m++) {
        groupArr[m]= arrL[m] + arrR[m] - 1;

        max = groupArr[m] > max? groupArr[m]:max
    }
    console.log(line - max)
}


发表于 2020-12-12 15:45:53 回复(0)
Python
小狗最6头像 小狗最6
while 1:
    try:
        n = int(input())
        list_0 = list(map(int, input().split()))
        def maxlong(list_):
            dp = [1 for i in range(len(list_))]
            res = 1
            for i in range(len(list_)):
                for j in range(i):
                    if list_[i] > list_[j] and dp[i]<dp[j]+1:
                        dp[i] = dp[j]+1
            return dp
        left = maxlong(list_0)
        right = maxlong(list_0[::-1])[::-1]
        temp = n
        for i in range(n):
            a = n-(left[i]+right[i]-1)
            if a < temp:
                temp =a
        print(temp)
    except:
        break
发表于 2020-09-01 19:18:03 回复(0)
C/C++
牛客601097166号头像 牛客601097166号
给定了一个数字列表，从左往右和从右往左，只需要找那一个数左侧和右侧，小于他的有效个数。比如如果是188 188 130 200 130 160 150，由于188 等于188 ，130小于188所以前三个书的有效个数都是1，让后200 大于他们所以就是两百本生的值和前面小于他的数对应的有效个数+1进行比较即max(当前位置本身的值，小于他的数的对应的有效个数+1）。从右侧往左同理。代码如下： 
#include <bits/stdc++.h>

using namespace std;

int main(){
    int N;
    while(cin >> N){
        vector<int> height(N, 0);
        for(int i = 0; i < N; i++){
            cin >> height[i];
        }
        vector<int> leftN(N, 0);
        vector<int> rightN(N, 0);
        for(int i = 0; i < N; i++){
            for(int j = i + 1; j < N; j++){
                if(height[i] < height[j])leftN[j] = max(leftN[j], leftN[i] + 1);
                if(height[N - i - 1] < height[N - j - 1])rightN[N - j - 1] = max(rightN[N - j - 1], rightN[N - i - 1] + 1);
            }
        }
        int max = 0;
        for(int i = 0; i < N; i++){
            //cout<< rightN[i] << endl;
            if(max < leftN[i] + rightN[i])max = leftN[i] + rightN[i];
        }
        cout << N -  max - 1 << endl;
    }
    
    return 0;
}

发表于 2020-08-24 21:43:56 回复(0)
卖报人头像 卖报人 
//两边递增子序列，每次二分查找插入
#include<iostream>
#include<vector>
using namespace std;

int fun(vector<int> &lps, int num) {
    if(lps.size() == 0) {
        lps.push_back(num);
        return 0;
    }
    int l = 0, r = lps.size()-1;
    int mid, pos = lps.size();
    while(l <= r) {
        mid = (l+r)/2;
        if(lps[mid] == num) {
            return mid;
        }
        else if(lps[mid] < num){
            l = mid + 1;
        }
        else {
            pos = pos < mid ? pos : mid;
            r = mid - 1;
        }
    }
    if(pos < lps.size()) {
        lps[pos] = num;
    }
    else {
        lps.push_back(num);
    }
    return pos;
}

int main() {
    int N;
    while(cin>>N){
        vector<int> v(N);
        vector<int> lps1, lps2;
        vector<int> res1(N), res2(N);
        int maxres = 0, tmp;
        for(int i = 0; i < N; i++) {
            cin>>v[i];
        }
        for(int i = 0; i < N; i++) {
            res1[i] = fun(lps1, v[i]);
        }
        for(int i = N-1; i >= 0; i--) {
            res2[i] = fun(lps2, v[i]);
        }

        for(int i = 0; i < N; i++) {
            tmp = res1[i] + res2[i];
            maxres = maxres > tmp ? maxres : tmp;
        }

        cout<<N - maxres - 1<<endl;
    }
    return 0;
}

发表于 2020-07-20 17:46:26 回复(0)
AA_Uli头像 AA_Uli 
# dp的二分优化，tail记录每个长度子序列的最后一个元素
def maxup(L):
    up = []
    tail, res = [0] * N, 0
    for num in L:
        i, j = 0, res
        while i < j:
            mid = (i + j) // 2
            if tail[mid] < num:
                i = mid + 1
            else:
                j = mid
        tail[i] = num
        up.append(j)
        if j == res: res += 1
    return up

while True:
    try:
        N = int(input())
        L = [int(c) for c in input().strip().split()]
        up = maxup(L)
        down = maxup(L[::-1])
        down = down[::-1]
        for i in range(N):
            up[i] += down[i]
        res = N - max(up) - 1
        print(res)
    except:
        break

发表于 2020-04-07 15:15:45 回复(0)
何小狗头像 何小狗 
import java.util.Scanner;

public class Main{
    public static void main(String [] args){
        Scanner sc=new Scanner(System.in);
        while(sc.hasNext()){
            int n=sc.nextInt();
            int [] positiveSequence=new int[n];
            int [] negativeSequence=new int[n];
            int [] LIS=new int[n];
            int [] LISR=new int[n];
            for(int i=0;i<n;i++){
                negativeSequence[n-i-1]=positiveSequence[i]=sc.nextInt();
                LIS[i]=LISR[i]=1;
            }
            for(int i=0;i<n;i++){
                for(int j=0;j<i;j++){
                    if(negativeSequence[i]>negativeSequence[j]){
                        LISR[i]=Math.max(LISR[j]+1,LISR[i]);
                    }
                    if(positiveSequence[i]>positiveSequence[j]){
                        LIS[i]=Math.max(LIS[i],LIS[j]+1);
                    }
                }
            }
            int sum=0;
            for(int i=0;i<n;i++){
                sum=Math.max(sum,LIS[i]+LISR[n-i-1]);
            }
            System.out.println(n-sum+1);
        }
    }
}

发表于 2020-02-23 12:47:17 回复(0)
mudamudamudamudamuda头像 mudamudamudamudamuda 
// nlogn 二分查找法的最长递增子序列
#include <iostream>
using namespace std;

//二分查找函数
int binsel(int *a, int i, int j, int t) {         if (i >= j) return i;     int mid = (i + j) / 2;     if (a[mid] < t && a[mid + 1] >= t) return mid + 1;     if (a[mid + 1] < t) return binsel(a, mid + 1, j, t);     else return binsel(a, i, mid, t);
}

//dp数组生成函数
void dparrraymake(int* a, int* dp, int *num, int n) {         int max = 1;     a[0] = num[0];     dp[0] = 0;     for (int i = 1; i < n; ++i) {         if (num[i] > a[max - 1]) {             a[max++] = num[i];             dp[i] = max - 1;         }         else {             dp[i] = binsel(a, 0, max - 1, num[i]);             a[dp[i]] = num[i];         }     }
}

int main() {     int *a, *ra, n, *dp, *rdp, *num, *rnum;     while (cin >> n) {         num = new int[n];         rnum = new int[n];         dp = new int[n];         rdp = new int[n];         a = new int[n];         ra = new int[n];         for (int i = 0; i < n; ++i) {             cin >> num[i];             rnum[n - i - 1] = num[i];         }         dparrraymake(a, dp, num, n);         dparrraymake(ra, rdp, rnum, n);         //找最大台上人数（不算自己）         int max = 0;                                 for (int i = 0; i < n; ++i) {             if (dp[i] + rdp[n - i - 1] > max) max = dp[i] + rdp[n - i - 1];         }         cout << n - max - 1<< endl;     }
}

编辑于 2019-07-06 15:07:53 回复(0)
Alexxu201805231919885头像 Alexxu201805231919885 
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
/*
递增序列指的是，在一个数列中，某个数的前面有多少个比它小的数（重复比它小的数只算作一个）；
如：     2 2 1 4 5 6
递增数列数  1 1 1 2 3 4

*/
using namespace std;

int getMax(const int& a, const int b)
{
    return a > b ? a : b;
}

void incSeqCnt(const vector<int>& queue, vector<int>& incCnt)
{
    for (int i = 1; i < queue.size(); i++)//求quque[i]的最大子序列计数，即它左边比它小的数（不重复的数）和它自己
    {
        for (int j = i - 1; j >= 0; j--)
        {
            if (queue[j] < queue[i])
            {
                incCnt[i] = getMax(incCnt[i], incCnt[j] + 1);//incCnt[i]：此时它的最大子序列计数，
                                                             //incCnt[j]+1：它本身加上queue[j]的最大子序列计数
            }
        }
    }
}

int main()
{

    int n;
    while(cin >> n){
    int h;
    vector<int> heights;
    for (int i = 0; i < n; i++)
    {
        cin >> h;
        heights.push_back(h);
    }
    vector<int> inc(n,1);//默认每个数的最大递增子序列数为1，即它自己
    vector<int> rInc(n, 1);//默认每个数的反方向最大递增子序列数为1，即它自己
    vector<int> total(n, 0);
    incSeqCnt(heights, inc);
    reverse(heights.begin(), heights.end());
    incSeqCnt(heights, rInc);
    int max = 0;
    for (int i = 0; i < inc.size(); i++)
    {
        total[i] = inc[i] + rInc[n-i-1]-1;//正反向计算最大子序列后，该数本身被加了两次，所以减去1
        if (max < total[i])max = total[i];
    }
    cout << n - max << endl;
    }
    return 0;
}

发表于 2019-04-01 12:26:48 回复(0)
鸡蛋黄头像 鸡蛋黄 
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

vector<int> maxinsub(vector<int> a){ //返回输入整型向量的最长递增子向量
    int n=a.size();
    vector<int> vi(n,1);
    for(int i=1;i<n;i++)
        for(int j=0;j<i;j++)
            if(a[j]<a[i]&&vi[j]+1>vi[i])
                vi[i]=vi[j]+1;
    return vi;
}

int main(){
    int n;
    while(cin>>n)
    {
        vector<int> vi; //还是注意反复利用的容器的定义位置，保证每次在往其中装东西时是空的，最好的办法就是在装东西的for循环前一行定义
        for(int i=0;i<n;i++)
        {
            int a; 
            cin>>a;
            vi.push_back(a);
        }
        vector<int> vmaxin=maxinsub(vi);
        reverse(vi.begin(),vi.end());
        vector<int> vmaxde=maxinsub(vi);
        reverse(vmaxde.begin(),vmaxde.end());
        int max=vmaxin[0]+vmaxde[0];
        for(int i=1;i<vmaxin.size();i++)
            if(vmaxin[i]+vmaxde[i]>max)
                max=vmaxin[i]+vmaxde[i];
        max-=1;
        cout<<n-max<<endl;
    }
    return 0;
}

发表于 2018-06-30 10:17:14 回复(0)
嗯嗯。。。头像 嗯嗯。。。 
import java.util.*;
public class Main {
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        Scanner sc = new Scanner(System.in);
        while(sc.hasNext()) {
            int num = sc.nextInt();
            int hight[] = new int[num];
            for(int i=0;i<num;i++) {
                hight[i] = sc.nextInt();
            }
            System.out.println(getResult(hight));
        }
    }
    public static int getResult(int hight[]) {
        //思路：记录正向递增和反向递增序列，相加-1最大的那个是保留的
        int dp1[] = new int[hight.length];
        int dp2[] = new int[hight.length];
        for(int i = 0;i<hight.length;i++){
            dp1[i] = 1;
            for(int j = i;j>=0;j--){
                if(hight[i]>hight[j]&&dp1[j]>=dp1[i]){
                    dp1[i] = dp1[j]+1;
                }
            }
        }
        for(int i = hight.length-1;i>=0;i--){
            dp2[i] = 1;
            for(int j = i;j<hight.length;j++){
                if(hight[i]>hight[j]&&dp2[j]>=dp2[i]){
                    dp2[i] = dp2[j]+1;
                }
            }
        }
        int sum = 0;
        for(int i = 0;i<hight.length;i++){
            if(dp1[i]+dp2[i]>sum)
                sum = dp1[i]+dp2[i];
        }
        return hight.length-(sum-1);
    }
}

编辑于 2018-07-24 22:34:01 回复(2)
C/C++
空空小飞头像 空空小飞 
最长递增子序列
#include<iostream>
using namespace std;
int MAX(int a, int b) {
	return a > b ? a : b;
}
int main() {
	int num;
	while (cin >> num) {
		int* height = new int[num];
		for (int i = 0; i < num; i++) {
			cin >> height[i];
		}
		int* dp1 = new int[num];//必须以i结束的递增子序列长度，则抽出同学数为i-dp1[i]
		int* dp2 = new int[num];//必须以i开始的递减子序列长度，则抽出同学数为num-i-dp2[i]-1
								//所以一共抽出num-1-dp1[i]-dp2[i]，求此最小值
		for (int i = 0; i < num; i++) {
			dp1[i] = 1; dp2[i] = 1;
		}
		for (int i = 0; i < num; i++) {
			int j = num - i - 1;
			for (int k = i - 1; k >= 0; k--) {
				if (height[i] > height[k])
					dp1[i] = MAX(dp1[k] + 1, dp1[i]);
				int m = num - k - 1;
				if (height[j] > height[m])
					dp2[j] = MAX(dp2[m] + 1, dp2[j]);
			}
		}
		int ans = num + 1 - dp1[0] - dp2[0];
		for (int i = 1; i < num; i++) {
			int tmp = num + 1 - dp1[i] - dp2[i];
			ans = ans < tmp ? ans : tmp;
		}
		cout << ans << endl;
	}
	return 0;
}

发表于 2017-07-27 09:53:06 回复(0)
CrazyCodingGirl头像 CrazyCodingGirl
求最长上升子序列和求最长下降子序列（从后往前的上升序列） 
#include<iostream>
#include <vector>
using namespace std;
int main()
{
	int N;
	while (cin >> N)
	{
		vector<int> arr(N, 0), inc(N, 1), des(N, 1);
		for (auto &i : arr)
			cin >> i;
		for (int i = 0; i < N; i++)
		{
			for (int j = 0; j < i; j++)
				if (arr[i]>arr[j] && (inc[j] + 1) > inc[i])
					inc[i] = inc[j] + 1;
		}
		for (int i = N - 1; i >= 0; i--)
		{
			for (int j = N - 1; j > i; j--)
				if (arr[i] > arr[j] && (des[j] + 1) > des[i])
					des[i] = des[j] + 1;
		}
		int ma = 0;
		for (int i = 0; i < N; i++)
		{
			if (inc[i] + des[i]>ma)
				ma = inc[i] + des[i];
		}
		cout << N - ma + 1 << endl;
	}
	return 0;
}

发表于 2017-07-26 17:46:58 回复(0)
Java
阿拉要洗澡头像 阿拉要洗澡

import java.util.Scanner;

//动态规划寻找最长递增子串
//先从右往左  再从左往右  把每个元素的在两次最大子串中对应的位置相加  意思就是    它左边的元素个数  加上它右边的元素个数  再减一 就是合唱队列   总人数减去合唱队人数 得到结果
//求最长递增子串算法看网页收藏夹--算法里的那个网站

//不需要用list记录所有递增子串
//只需要记录每个数字的最大子串元素数 ，下一个数字的最大子串元素数    等于     之前的数字中小于它的最大子串元素最多的数字    对应的子串数加一
public class Main{
    public static void main(String[] args){
        Scanner sc=new Scanner(System.in);
        while(sc.hasNext()){

            int num=sc.nextInt();
            
            if(num<=2) {
           
            System.out.println(0);
            }
            
            
            
            
            int[] members=new int[num];//存储每个数字
            int[] numOfLeft=new int[num];//存储每个数字从左往右遍历查找最长字串时候的对应的最长字串元素数
            int[] numOfRight=new int[num];//存储每个数字从右往左遍历查找最长字串时候的对应的最长字串元素数
            

            for(int i=0;i<num;i++){
                
                members[i]=sc.nextInt();
                
                
            }
            
            
            
            
            //从左到右查找每个数字对应的最长字串数目
            for(int i=0;i<num;i++){
           
           
                
            if(i==0) {
           
            numOfLeft[i]=1;
           
           
            }else {
           
           
            int maxSubNum=Integer.MIN_VALUE;            
           
            //遍历已有的结果 找出之前的最长字串
            for(int j=0;j<i;j++) {
           
            if(numOfLeft[j]>maxSubNum && members[j]<members[i]) {
           
            maxSubNum=numOfLeft[j];
           
            }
           
           
            }
           
         
            if(maxSubNum!=Integer.MIN_VALUE)
                    {
                    numOfLeft[i]=maxSubNum+1;
                    }else {
                    numOfLeft[i]=1;
                    }
             

            }

           
                
            }

            //从右到左边查找每个数字对应的最长字串
            for(int i=num-1;i>=0;i--){
           
           
            if(i==num-1) {
           
            numOfRight[i]=1;
           
           
            }else {
           
           
            int maxSubNum=Integer.MIN_VALUE;            
           
            //遍历已有的结果 找出之前的最长字串
            for(int j=num-1;j>i;j--) {
           
            if(numOfRight[j]>maxSubNum && members[j]<members[i]) {
           
            maxSubNum=numOfRight[j];
           
            }
           
           
            }
           
                    if(maxSubNum!=Integer.MIN_VALUE)
                    {
                    numOfRight[i]=maxSubNum+1;
                    }else {
                    numOfRight[i]=1;
                    }
           
            //System.out.println("numOfRight[i] "+i+" "+numOfRight[i]);
            }
           
                
            }
            
            
            
            
            int result[]=new int[num];
            int max=Integer.MIN_VALUE;
            
            for(int i=0;i<num;i++){
           
           
            result[i]=numOfRight[i]+numOfLeft[i];
            if(max<result[i]) {
           
            max=result[i];
           
            }
           
           
            }

            System.out.println(num+1-max);
 
        }

    }

}

发表于 2017-06-27 16:38:55 回复(0)
Java
昵称真难取头像 昵称真难取
import java.util.Scanner;
public class Main{
    public static int[] dp(int a[]){/动态规划  最长增序列
        int l=a.length;
        int count[]=new int[l];
        count[0]=1;
        for(int i=1;i<l;i++){
            int max=0;
            for(int j=0;j<i;j++){
                if(a[i]>a[j]){
                    if(max<count[j])
                    max=count[j];
                }
            }
            count[i]=max+1;
        }
        return count;
    }
    public static int sing(int a[]){
        int max=0,tmp=0;
        int l=a.length;
        int b[]=new int[l];//存a的逆序
        int count1[]=new int[l];
        int count2[]=new int[l];
        for(int i=l-1;i>=0;i--){
            b[l-i-1]=a[i];
        }
        count1=dp(a);//正序
        count2=dp(b);//逆序
        for(int i=0;i<l;i++){
            tmp=count1[i]+count2[l-i-1];
            if(tmp>max){
            max=tmp;
            }
                
            
        }
        return l-max+1;
    }
    public static void main(String args[]){
       Scanner sc=new Scanner(System.in);
        while(sc.hasNext()){
            int n=sc.nextInt();
            int a[]=new int[n];
            for(int i=0;i<n;i++){
                a[i]=sc.nextInt();
            }
            int res=sing(a);
            System.out.println(res);
        }
    }
}
发表于 2017-03-23 10:49:55 回复(0)
BrainerGao头像 BrainerGao 
import java.util.*;
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        while(in.hasNext()) {
            int N = in.nextInt();
            int[] heights = new int[N];
            int[] inc_hei = new int[N];
            int[] dec_hei = new int[N];
            int tmp = 0;
            for(int i = 0; i < N; i++) {
                heights[i] = in.nextInt();
                inc_hei[i] = 1;
                dec_hei[i] = 1;
            }
            for(int i = 1; i < N; i++) {
                for(int j = 0; j < i; j++) {
                    if(heights[j] < heights[i] && inc_hei[j] + 1 > inc_hei[i])
                        inc_hei[i] = inc_hei[j] + 1;
                }
            }
            for(int i = N-2; i >= 0; i--) {
                for(int j = N-1; j > i; j--) {
                    if(heights[j] < heights[i] && dec_hei[j] + 1 > dec_hei[i])
                        dec_hei[i] = dec_hei[j] + 1;
                }
            }
            for(int i = 0; i < N; i++) {
                if(inc_hei[i] + dec_hei[i] - 1 > tmp)
                    tmp = inc_hei[i] + dec_hei[i] - 1;
            }
            System.out.println(N - tmp);
        }
        in.close();
    }
}

发表于 2017-03-16 21:08:19 回复(1)
当当当档头像 当当当档 
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);
		while (scanner.hasNext()) {
			String str_num = scanner.nextLine();
			int num = Integer.parseInt(str_num);
			String [] str_height = scanner.nextLine().split(" ");
			int [] height = new int[num];
			for (int i = 0; i < num; i++) {
				height[i] = Integer.parseInt(str_height[i]);
			}
			int [] d = new int[num];
			d[0] = 1;
			int [] e = new int[num];
			e[num-1] = 1;
			for(int i = 1;i < num;i++){
				int max = 1;
				for(int j = i - 1;j >= 0;j--){
					if(height[j]<height[i]&&d[j]+1>max){
						max = d[j]+1;
					}
				}
				d[i] = max;
			}
			for(int i = num-1;i > 0;i--){
				int max = 1;
				for(int j = i;j < num;j++){
					if(height[j]<height[i]&&e[j]+1>max){
						max = e[j]+1;
					}
				}
				e[i] = max;
			}
			int max_pq = 0;
			for (int i = num-1; i > 0; i--) {
				if(e[i]+d[i]>max_pq) max_pq = e[i]+d[i];
			}
			System.out.println(num-max_pq+1);
		}
	}
}

发表于 2017-02-24 14:35:59 回复(0)
qfxyx头像 qfxyx 
//动态规划 import java.util.*;

public class Main {

	public static void main(String[] args) {
		
		Scanner scanner  = new Scanner(System.in);
		while(scanner.hasNext()){
		  int n1=scanner.nextInt();
		  int[] arr =new int[n1];
		  for(int i=0;i<n1;i++){
			  arr[i]=scanner.nextInt();
		  }
		  System.out.println(getValue(arr));
		}
	
		}
	public static int getValue(int[] arr){
		int total=-1;
		if (arr==null) {
			return total;
		}
		int[] temp1 = new int[arr.length];
		int[] temp2 = new int[arr.length];
		temp1[0]=1;
		temp2[arr.length-1]=1;
		for(int i =1;i<temp1.length;i++){
			int max = 1;
			for (int j = 0; j < i; j++) {
				if (arr[j]<arr[i]&&temp1[j]+1>max) {
					max=temp1[j]+1;
				}
			}
			temp1[i]=max;
		}
		for(int i =temp2.length-2;i>0;i--){
			int max = 1;
			for (int j = temp2.length-1; j >i; j--) {
				if (arr[j]<arr[i]&&temp2[j]+1>max) {
					max=temp2[j]+1;
				}
			}
			temp2[i]=max;
		}
		int count = 0;
		for(int i=0;i<temp1.length;i++){
			if (temp1[i]+temp2[i]>count) {
				count=temp1[i]+temp2[i];
			}
		}
		total=arr.length-count+1;
		return total;
	}
	
}


发表于 2016-09-19 23:46:03 回复(0)
ClusterSocketListenThread头像 ClusterSocketListenThread 
#include <iostream>
using namespace std;

int main(void)
{
	int n;
	while( cin >> n)
	{
		int crew[n], A[n], B[n], C[n];
		int i,j,max;
		for (i = 0; i < n; i++)
			cin >> crew[i];
		for (i = 0; i < n; i++)
		{
			max = 0;
			for (j = 0; j < i; j++)
				if (crew[i] > crew[j] && B[j] > max)
					max = B[j];
			B[i] = max + 1;
		}
		for (i = n-1; i >= 0; i--)
		{
			max = 0;
			for (j = n-1; j > i; j--)
				if (crew[i] > crew[j] &&  C[j] > max)
					max = C[j];
			C[i] = max + 1;
		}
		max = 0;
		for (i = 0; i < n; i++)
		{
			A[i] = B[i] + C[i] -1;
			if (A[i] > max)
				max = A[i];
		}
		cout << n - max << endl;
	}
} 

考虑每一个人为中间那个最大的情况

发表于 2016-08-09 10:46:50 回复(2)
C/C++
Allen解神头像 Allen解神

首先计算每个数在最大递增子串中的位置

186  186  150  200  160  130  197  200   quene

1      1      1      2       2      1      3     4       递增计数


然后计算每个数在反向最大递减子串中的位置--->计算反向后每个数在最大递增子串中的位置

200  197  130  160  200  150  186  186   反向quene

1      1      1       2     3      2      3       3      递减计数


然后将每个数的递增计数和递减计数相加

186  186  150  200  160  130  197  200   quene

1      1      1      2       2     1      3      4       递增计数

3      3      2      3       2     1      1      1       递减计数

4      4      3      5       4     2      4      5       每个数在所在队列的人数+1（自己在递增和递减中被重复计算）


如160这个数

在递增队列中有2个人数

150  160

在递减队列中有2个人数

160  130

那么160所在队列中就有3个人

150  160  130


每个数的所在队列人数表达就是这个意思


总人数 - 该数所在队列人数 = 需要出队的人数 


#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

void calIncSub(vector<int> quene, vector<int> &Num){
	for(int i=1;i<quene.size();i++)
		for(int j=i-1;j>=0;j--)
			if(quene[j]<quene[i] && Num[i]<Num[j]+1)	//找到前面比当前小的，且【能获得的最大子串计数】
				Num[i]=Num[j]+1;
}

int main(){
	int n;
	int h;
    
    while(cin>>n){
        vector<int> quene;
        vector<int> incNum(n,1);	//初始化为n个1
        vector<int> decNum(n,1);	
        vector<int> totalNum;
        for(int i=0;i<n;i++){
            cin >> h;
            quene.push_back(h);    
        }
        calIncSub(quene,incNum);	//找递增子串计数
        reverse(quene.begin(),quene.end());	//翻转，即找反向的子串计数
        calIncSub(quene,decNum);
        reverse(decNum.begin(),decNum.end());	//反向递增即正向递减
        int max=0;
        for(int i=0;i<n;i++){
            totalNum.push_back(incNum[i]+decNum[i]);
            if(totalNum[i]>max)
                max=totalNum[i];
        }
        cout << n-max+1 <<endl;
    }	
	return 0;
}

编辑于 2016-09-09 16:40:42 回复(44)
提交观点

问题信息

动态规划 队列
难度：
506条回答 63126浏览

热门推荐

通过挑战的用户

查看代码

相关试题

合唱队

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号