首页 > 试题广场 > 合唱队
[编程题]合唱队
  • 热度指数:66277 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 32M,其他语言64M
  • 算法知识视频讲解

计算最少出列多少位同学,使得剩下的同学排成合唱队形

说明:

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

请注意处理多组输入输出!



输入描述:

整数N



输出描述:

最少需要几位同学出列

示例1

输入

8
186 186 150 200 160 130 197 200

输出

4

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

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 回复(39)

算法:动态规划
用到概念:递增子序列
思想:

所有比m[i]小的数都可以作为倒数第二个数,在这些第二个数中,以哪个数结尾的递增子序列最大,就以那个数作为倒数第二个数 。以本身作为最后一个数,前面没有比它小的,则子序列为1.


借用一楼用c编的注释,写的很清楚,拿来用下:

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

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

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

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


import java.util.Scanner;

public class Main {
public static void main(String[] args) {
    Scanner in = new Scanner(System.in);
    while (in.hasNext()) {
        int num = in.nextInt();
        if(num<=2){
            System.out.println(0);
        }
        int[] members=new int[num];//存储每一个数据元素
        int[] left_queue=new int[num];//数据元素从左到右对应的最大递增子序列数
        int[] right_queue=new int[num];//数据元素从右到左对应的最大递增子序列数
        for(int i=0;i<num;i++){//初始化各个数组数据
            members[i]=in.nextInt();
            left_queue[i]=1;
            right_queue[i]=1;
        }
        for(int i=0;i<num;i++){
            for(int j=0;j<i;j++){
                if(members[i]>members[j]&&left_queue[j]+1>left_queue[i])
                    left_queue[i]=left_queue[j]+1;
            }
        }
        for(int i=num-1;i>=0;i--){
            for(int j=num-1;j>i;j--){
                if(members[i]>members[j]&&right_queue[j]+1>right_queue[i])
                    right_queue[i]=right_queue[j]+1;                   
            }
        }
        int max=0;
        for(int i=0;i<num;i++){
            if(left_queue[i]+right_queue[i]>max)
                max=left_queue[i]+right_queue[i];
        }
        System.out.println(num-max+1);
    }
}
}
编辑于 2017-07-11 18:22:48 回复(3)
来说一下我的思路,两遍最长递增子序列,第一遍从左往右,第二遍从右往左,然后把两遍动态规划的结果相加,取最大的那个,比如8 186 186 150 200 160 130 197 200,第一遍dp的结果是 1 1 1 2 2 1 3 4,第二遍dp的结果为3 3 2 3 2 1 1 1,那么相加最大是5,所以需要出列的同学个数就是8-5+1=4.代码如下:
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

// 基本思路,两遍最长递增子序列,并找和最大
int main(void)
{
	int n;
	while (cin >> n)
	{
		int tmp;
		vector<int> queue;
		vector<int> dp_1(n, 1);
		vector<int> dp_2(n, 1);
		
		for (int i = 0; i < n; ++i)
		{
			cin >> tmp;
			queue.push_back(tmp);
		}

		// 第一遍dp
		for (int i = 0; i < n; ++i)
		{
			for (int j = i - 1; j >= 0; --j)
			{
				if (queue[i] > queue[j] && dp_1[i] < dp_1[j] + 1)
					dp_1[i] = dp_1[j] + 1;
			}
		}

		std::reverse(queue.begin(), queue.end());
		// 第二遍dp
		for (int i = 0; i < n; ++i)
		{
			for (int j = i - 1; j >= 0; --j)
			{
				if (queue[i] > queue[j] && dp_2[i] < dp_2[j] + 1)
					dp_2[i] = dp_2[j] + 1;
			}
		}
		std::reverse(dp_2.begin(), dp_2.end());

		int max = -1;
		int sum;
		for (int i = 0; i < n; ++i)
		{
			sum = dp_1[i] + dp_2[i];
			if (sum > max)
			{
				max = sum;
			}
		}
		cout << n - max + 1 << endl;
	}
	return 0;
}

发表于 2016-08-11 21:26:25 回复(30)
对于这道题的含义以及解题思路可能有些人不太明白,结合上面几位大佬的解释,提出一下个人见解:
1. 对于题目,我个人理解是所有人都已经站好位,不能再改变位置了,只能从当中去掉人组成合唱队。同时,可以考虑中间的人两边没有人的情况(比如两头的两个人,或者这个人太矮周围的人都比他高的情况),但是这种情况基本被pass掉。
2. 对于1楼大佬所说的最长递增子序列,我个人见解是:
比如题中所给出的示例:186 186 150 200 160 130 197 200,先看每个人的左边可能出现最多的人。首先如果第一个数186在中间,左边没有数,就自己一个人,所以是1;第二个数186因为左边那个人跟他一边高,没有比他矮的了,所以也是1;第三个数150,左边的人都比他高,他如果是中间的话左边也他自己一个人,所以还是1;第四个数200,因为不能换位置,所以只能留186或者150,加上自己,就是2...最后再以197为例,左边保留150,160是左边人最多的情况,再加上自己,就是3。所以每个人左边人做多的情况(加上自己)就是(186)1 1 1 2 2 1 3 4(200)。同理,看一下每个人右边可能出现最多的人,这时我们从后往前看。200在最右面,所以自己一个人,是1;197最右面没有比他矮的,自己,是1...160左边一个比他矮的,所以算上自己是2,以此类推。所以每个人右边人做多的情况(加上自己)就是(186)3 3 2 3 2 1 1 1(200)
3. 所以将上面两个划横线的对应相加,就可以得到自己如果是中间的那个人,可以得到的最大的合唱队人数。当然,自己加了两遍,所以得减掉一个自己。另外题目问的是最少去掉的人,所以最后的结果:
总人数 - 该数所在队列人数 = 需要出队的人数
4. 本人所编代码中最核心的部分是(以左最长递增子序列为例)
if l[j]<l[i] and ans[j]+1>ans[i]:  ans[i]=ans[j]+1
代表的意思是目前的这个ans[j] + 1是否比之前得到的 ans[i] 要大(ans[i]默认是1,表示自己一个人)。假设之前ans[i] = 4,现在ans[j] +  1 = 3,那么就不需要更新。

代码如下:
# 每个人的左边出现的最多人(输出左_最长递增子序列)
def left_max(l):#l为站成一排的同学序列
    ans=[1]*len(l)
    for i in range(len(l)):# 每个人的游标(从前往后)
        for j in range(i):# 这个人前面每个人的游标
            if l[j]<l[i] and ans[j]+1>ans[i]:
                ans[i]=ans[j]+1
    return ans # 1 1 1 2 2 1 3 4

# 每个人的右边出现的最多人(输出右_最长递增子序列)
def right_max(l):
    ans=[1]*len(l)
    for i in range(len(l)-1,-1,-1):# 每个人的游标(从后往前)
        for j in range(i+1,len(l)):# 这个人后面每个人的游标
            if l[j]<l[i] and ans[j]+1>ans[i]:
                ans[i]=ans[j]+1
    return ans # 3 3 2 3 2 1 1 1

while True:
    try:
        N=int(input())(1177)#8
        tall_li_str=input().split()
        tall_li_int=[int(v) for v in tall_li_str]#[186,186,150,200,160,130,197,200]
        left_li=left_max(tall_li_int)
        right_li=right_max(tall_li_int)
        sum_li=[]#left_li和right_li加和,可以得到每个人如果是中间那个人的话,合唱队最长是多少(自己算两遍)
        for i in range(len(left_li)):
            sum_li.append(left_li[i]+right_li[i])
        print(N-max(sum_li)+1)#题中问的是最少去几人,也就是总人数减去合唱队最多人数
        # 另外加和时自己算了两遍,还得再减去一遍
    except:
        break



编辑于 2020-03-01 16:46:01 回复(10)
import java.util.*;

public class Main{
    public static void main(String[] args){
        Scanner s = new Scanner(System.in);
        while(s.hasNext()){
            int n = s.nextInt();
            int temp = 0;
            int[] Inc = new int[n];
            int[] Dec = new int[n];
            int[] arr = new int[n];
            for(int i = 0; i < n; i++){
                arr[i] = s.nextInt();
            }
            Inc[0] = 1;
            for(int i = 1; i < n; i++){
                Inc[i] = 1;
                for(int j = 0; j < i; j++){
                    if(arr[j] < arr[i] && Inc[j] + 1 > Inc[i]){
                        Inc[i] = Inc[j] + 1;
                    }
                }
            }
            Dec[n - 1] = 1;
            for(int i = n -2; i >= 0; i--){
                Dec[i] = 1;
                for(int j = n - 1; j > i; j--){
                    if(arr[j] < arr[i] && Dec[j] + 1 > Dec[i]){
                        Dec[i] = Dec[j] + 1;
                    }
                }
            }
            for(int i = 0; i < n; i++){
                if(Inc[i] + Dec[i] - 1 > temp)
                    temp = Inc[i] + Dec[i] - 1;
            }
            System.out.println(n - temp);
        }
    }
}

发表于 2016-07-29 16:42:03 回复(5)
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <iomanip>
#include <math.h>
using namespace std;

int main()
{
	int n;
	while (cin >> n)
	{
		vector<int> vec(n), dp(n), dq(n);
		int i, k, j, ma = 0;
		for (i = 0; i < n; ++i)
		{
			cin >> vec[i];
			dp[i] = 1;
			dq[i] = 1;
		}
		for (i = 1; i < n; ++i)
		{
			for (j = 0; j < i; ++j)
			{
				if (vec[i] > vec[j])
					dp[i] = max(dp[i], dp[j] + 1);
			}
		}
		for (i = n - 2; i >= 0; --i)
		{
			for (j = n - 1; j > i; --j)
			{
				if (vec[i] > vec[j])
					dq[i] = max(dq[i], dq[j] + 1);
			}
		}
		for (i = 0; i < n; ++i)
			ma = max(ma, dp[i] + dq[i] - 1);
		cout << n - ma << endl;
	}
	return 0;
}

发表于 2016-07-12 23:25:50 回复(3)
import bisect

def deal(l,res):
    b    = [float('inf')]*len(l)
    b[0] = l[0]
    res  = res+[1]
    for i in range(1,len(l)):
        pos =bisect.bisect_left(b,l[i])
        b[pos]=l[i]
        res += [pos+1]
    return res

def main(n,s):
    n = int(n)
    s = list(map(int,s.split()))
    dp1, dp2=[], []
    dp1 =deal(s,dp1)
    dp2 =deal(s[::-1],dp2)[::-1]
    return n-max(map(sum,zip(dp1,dp2)))+1

while 1:
    try:
        print(main(input(),input()))
    except:
        exit()

发表于 2020-02-22 22:25:31 回复(1)
将题目反向思考:它要我们找出需要排出去的数字个数,我们可以去找最后剩余的数字个数;将最后剩余的数看成一个三角形,它有一个顶点,其次是两条分别递增和递减的数字序列,因此我们可以将问题转换为求解当前位置前递增长度和后递减长度之和最大的那个位置的值,然后用总长度减去这个长度就为最终答案
这里需要注意:因为我使用的是从左到右和从右到左遍历最长递增子序列长度值,for循环中一般是分别从2和从n-1开始,所以就会忽略了两次遍历的头部初始化,所以我第一次提交90%,这里需要注意的是两次遍历的头部初始化1
import java.util.Scanner;
public class Main{          public static void main(String[] args){         Scanner in = new Scanner(System.in);         while(in.hasNext()){             int n = in.nextInt();             int num[] = new int[n+1];             for(int i=1; i<=n; i++){                 num[i] = in.nextInt();             }             //从左到右记录最长递增子序列长度值             int ltr[] = new int[n+1];             ltr[1] = 1;             for(int i=2; i<=n; i++){                 ltr[i] = 1;                 for(int j=1; j<i; j++){                     if(num[i] > num[j] && ltr[j]+1 > ltr[i]){                         ltr[i] = ltr[j]+1;                     }                 }             }                          //从右到左记录最长递增子序列长度值             int rtl[] = new int[n+1];             rtl[n] = 1;             for(int i=n-1; i>=1; i--){                 rtl[i] = 1;                 for(int j=n; j>i; j--){                     if(num[i] >num[j] && rtl[i] < rtl[j]+1)                         rtl[i] = rtl[j]+1;                 }             }                          //注意,temp为剩余的个数,最终值要n-temp             int temp = 0;             for(int i=1; i<=n; i++){                 if(ltr[i]+rtl[i]-1 > temp)                     temp = ltr[i]+rtl[i]-1;             }                          System.out.println(n-temp);         }         in.close();     }
}

发表于 2017-09-18 10:50:19 回复(0)
package 合唱队问题;

import java.util.Arrays;
import java.util.Scanner;

/**
 * 分开写每个功能:递增LIS,递减LIS,叠加-1找最大值
 * 
 * @author hest0
 *
 */
public class 合唱队问题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();
			System.out.println(function(a));
		}
		sc.close();
	}

	// 实现合唱队排队的功能
	public static int function(int[] a) {
		int n = a.length;

		if (n == 0)
			return 0;

		int[] dpForword = dpForword(a);
		int[] dpBackward = dpBackward(a);

		System.out.println(Arrays.toString(dpForword));
		System.out.println(Arrays.toString(dpBackward));

		int max = 0;

		for (int i = 0; i < n; i++) {
			max = Math.max(dpForword[i] + dpBackward[i], max);
		}

		return n - (max - 1);
	}

	// 正向递增最长子序列
	public static int[] dpForword(int[] a) {
		int n = a.length;
		int[] dp = new int[n];

		dp[0] = 1;

		for (int i = 0; i < n; i++) {
			dp[i] = 1;
			for (int j = 0; j < i; j++) {
				if (a[j] < a[i] && dp[j] + 1 > dp[i])
					dp[i] = dp[j] + 1;
			}
		}

		return dp;
	}

	// 逆向递增最长子序列
	public static int[] dpBackward(int[] a) {
		int n = a.length;
		int[] dp = new int[n];

		dp[n - 1] = 1;

		for (int i = n - 1; i >= 0; i--) {
			dp[i] = 1;
			for (int j = n - 1; j > i; j--) {
				if (a[j] < a[i] && dp[j] + 1 > dp[i])
					dp[i] = dp[j] + 1;
			}
		}

		return dp;
	}

}


编辑于 2016-09-03 20:41:11 回复(2)
//解(1)
//LIS的DP解法,时间复杂度O(N2).
#include<iostream>
#include<vector>
using namespace std;

int main(){   
    int n = 0;
    while(cin>>n){
        vector<int> input(n, 0);
        for(int i = 0; i < n; ++i) 
            cin>>input[i];
        vector<int> left(n, 1);//从左向右遍历,在left数组中记录对应位置的lis的长度
        vector<int> right(n, 1);//从右向左遍历,在right数组中记录对应位置的lis的长度
        for(int i = 1; i < n; ++i){
			for(int j = 0; j < i; ++j){
				if(input[j] < input[i] && left[j] + 1 > left[i])
                    left[i] = left[j] + 1; 
            }
        }
        for(int i = n - 2; i >= 0; --i){
			for(int j = n - 1; j > i; --j){
				if(input[j] < input[i] && right[j] + 1 > right[i])
                    right[i] = right[j] + 1;         
            }
        }
        int maxLen = 0;
        for(int i = 0; i < n; ++i){
            if(left[i] + right[i] > maxLen)
                maxLen = left[i] + right[i];
        }
        cout<<(n-maxLen+1)<<endl;
    }
    return 0;
}

//解(2):
//LIS问题O(NlgN)的解法。具体思路见链接:http://qiemengdao.iteye.com/blog/1660229 #include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

//修改的二分搜索,返回待搜数据在数组中的位置
int biSearch(const vector<int> & tmp, int num){
    int pos = 0;
    int s = 0, e = tmp.size();
    while(s <= e){
        int mid = (e - s)/2 + s;
        if(num > tmp[mid]){
            s = mid + 1;
        }
        else if(num < tmp[mid]){
            e = mid - 1;
        }
        else return mid;
    } 
    return s;
}

//O(NlgN)的解法
vector<int> LIS(const vector<int> & vec){
    int sz = vec.size();
    vector<int> ret(sz, 0); //返回vec每个对应位置的的LIS长度
    vector<int> tmp;        //临时数组,用于记录对应位置的LIS的最小末尾
    for(int i = 0; i < sz; ++i){
        if(tmp.empty())
            tmp.push_back(vec[i]);
        else if(vec[i] > tmp.back())
            tmp.push_back(vec[i]);
        else{
            int pos = biSearch(tmp, vec[i]);
            tmp[pos] = vec[i]; //替换
        }
        ret[i] = tmp.size();
    }
    return ret;
}

int main(){   
    int n = 0;
    while(cin>>n){
        vector<int> input(n, 0);
       for(int i = 0; i < n; ++i) 
        cin>>input[i];         
        vector<int> left = LIS(input);
            reverse(input.begin(), input.end());
            vector<int> right = LIS(input);
            int maxLen = 0;
            for(int i = 0; i < n; ++i){
                if(left[i] + right[n-1-i] > maxLen)
                    maxLen = left[i] + right[n-1-i];
        }
        cout<<(n-maxLen+1)<<endl;
    }
    return 0;
}

编辑于 2017-06-20 16:16:54 回复(0)
import bisect

#动态规划获得最大递增自序列,时间复杂度O(n*n)
# def ascMax(l, dp):
#     dp += [1]
#     for i in range(1, len(l)):
#         tmp = 0
#         for j in range(0, i):
#             if l[j] < l[i]:
#                 tmp = max(dp[j], tmp)
#         dp += [tmp + 1]

#二分法获取最大递增子序列,时间复杂度O(nlogn)
def ascMax(l, dp):
    dp += [1]
    b = [float('inf') for i in range(len(l))]#初始化b数组为无穷大
    b[0] = l[0](1844)#第一个元素自己就是最大递增子序列
    for i in range(1, len(l)):
        pos = bisect.bisect_left(b, l[i])
        b[pos] = l[i]
        dp += [pos + 1]

while True:
    try:
        N = int(input())
        H = list(map(int, input().split(' ')))
        dp_1, dp_2 = [], []
        ascMax(H, dp_1)
        ascMax(H[::-1], dp_2)
        dp = []
        for i in range(0, N):
            dp += [dp_1[i] + dp_2[N-i-1] - 1]
        print(N - max(dp))
    except:
        break

编辑于 2020-03-09 00:00:46 回复(0)
/*   借鉴顶楼兄弟的思路,但表述稍许不清,所谓递增计数,实际上就是以当前值为结尾的序列的最长递增子序列长度,
 比如以197结尾的序列中,最长递增子序列为150,160,197,故递增计数为3,由于三个数并不相邻,故称其为“子串”不妥。
     所谓“递增计数”就是用动态规划求最长递增子序列中的“dp”:
     dp[i]={max(dp[j])+1,j<i且a[j]<a[i]},
     翻译成汉字:以a[i]结尾的序列的最长递增子序列长度,等于以a[i]之前的一个数j(该数的值小于a[i]来保证递增并
且max是指我们要取使dp[j]最大的这个数)结尾的序列的最长递增子序列长度算上a[i]本身。
     代码实现时,我们需要遍历在i之前的所有位置j(从0到i-1),找出满足条件a[j]<a[i]的dp[j],求出max(dp[j])+1
即为dp[i]的值。
*/
import java.util.*;
public class Main{
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while(sc.hasNextLine()){
            int n = Integer.parseInt(sc.nextLine());
            String str = sc.nextLine();
            System.out.println(removeNo(str,n));
        }
    }

    public static int removeNo(String str,int n){
        String[] stra = str.split(" ");
        int[] height = new int[n];//分别为正序和逆序的整型数组
        int[] heightopp = new int[n];
        for(int i=0;i<n;i++){
            height[i] = Integer.parseInt(stra[i]);
        }
        for(int i=0;i<n;i++){
            heightopp[i] = height[n-i-1];
        }
         int[] dp = Maxsub(height,n);//递增计数
         int[] dpopp = Maxsub(heightopp,n);//递减计数(逆序)
         int[] sum = new int[n];
         for(int i=0;i<n;i++){
             sum[i] = dp[i]+dpopp[n-i-1];//相加时要将递减计数倒过来
         }
        int max = 0;//求递增计数与递减计数之和的最大值
        for(int i=0;i<n;i++){
            max = sum[i]>max?sum[i]:max;
        }
        return n-(max-1);//返回出列人数
    }

    public static int[] Maxsub(int[] stra,int n){//按公式dp[i]={max(dp[j])+1,j<i且a[j]<a[i]}求dp[i]
        int[] dp = new int[n];
        for (int i=0;i<n;i++){
            dp[i] = 1;
            for (int j=0;j<i;j++) {
                 if (stra[j]<stra[i]) {
                   dp[i] = Math.max(dp[i], dp[j]+1);
                }
            }
        }
        return dp;
    }
}
发表于 2019-09-24 22:18:41 回复(0)
#include<stdio.h>

int main()
    {
    int n=0;
    while(scanf("%d",&n)!=EOF)
        {
        if(n<=0)
            printf("0\n");
        int tall[n];
        int left_queue[n];            //左排队
        int right_queue[n];           //右排队 
        for(int i=0;i<n;i++)
        {
            scanf("%d",&tall[i]);
            left_queue[i]=1;
            right_queue[i]=1;
        }
            
        for(int i=0;i<n;i++)        
            {
            for(int j=0;j<i;j++)
                {
                if(tall[i]>tall[j]&&left_queue[j]+1>left_queue[i])  //一种分治思想,只要i比前面的高,最大长度就是前面那个最大长度+1
                    left_queue[i]=left_queue[j]+1;     
            }
        }
        for(int i=n-1;i>=0;i--)        
            {
            for(int j=n-1;j>i;j--)
                {
                if(tall[i]>tall[j]&&right_queue[j]+1>right_queue[i])
                    right_queue[i]=right_queue[j]+1;     
            }
        }

        int max=0;
        for(int i=0;i<n;i++)
            {
            if(left_queue[i]+right_queue[i]>max)
                max=left_queue[i]+right_queue[i];
        }
        printf("%d\n",n-max+1);             //中间点减了2次,最后需要+1
    }
}

发表于 2017-05-30 11:35:38 回复(1)
#include<stdio.h>
int main()
{
	int m=0,n,a[5000],b[5000],c[5000],d[5000];
	while(scanf("%d",&n)!=EOF)
	{
	for(int i=0;i<n;i++)
		scanf("%d",&a[i]);
	for(int i=0;i<n;i++)
	{
		b[i]=1;
		c[i]=1;
	}
	for(int i=0;i<n;i++)
		for(int j=i+1;j<n;j++)
			if(a[j]>a[i]&&b[j]<b[i]+1)
				b[j]=b[i]+1;
	for(int i=n-1;i>=0;i--)
		for(int j=i-1;j>=0;j--)
			if(a[j]>a[i]&&c[j]<c[i]+1)
				c[j]=c[i]+1;
	for(int i=0;i<n;i++)
	{
		d[i]=b[i]+c[i];
		if(d[i]>m)
			m=d[i];
	}
	printf("%d\n",n-m+1);
	}
	return 0;
}
不知道为什么只有60%pass

发表于 2017-05-05 14:56:44 回复(0)

用a[i]表示输入的数字;

用left[i]表示从左边第一个数到第i个数最大的增长序列个数;

用right[i]表示从右边最后一个数到第i个数最大的增长序列个数;

结果就是 n - max(left[i] + right[i] -1)

解释:

max(left[i] + right[i] - 1)表示的是合唱队最多的人数,相反的情况就是最少需要几位同学出列

代码中最关键的一行是 left[i] < left[j] + 1 代表的意思是目前的这个left[j] + 1是否比之前得到的 left[i] 要大。假设之前left[i] = 4,现在left[j] +  1 = 3,那么就不需要更新。

#include "stdio.h" #include "stdlib.h" int main() { int num; while(scanf("%d",&num)!=EOF) { int ans=0,i,j,a[5000],left[2000],right[2000]; for(i=0;i<num;i++) scanf("%d",&a[i]); for(i=0;i<num;i++) { left[i]=1; for(j=0;j<i;j++) if(a[j]<a[i]&&(left[j]+1>left[i])) left[i]=left[j]+1; } for(i=num-1;i>=0;i--) { right[i]=1; for(j=num-1;j>i;j--) if(a[j]<a[i]&&(right[j]+1>right[i])) right[i]=right[j]+1; } for(i=0;i<num;i++) if(left[i]+right[i]-1>ans) ans=left[i]+right[i]-1; printf("%d\n",num-ans); } }

发表于 2017-03-23 11:16:19 回复(2)
def get_index(nums,target):
    low,high=0,len(nums)-1
    pos=len(nums)
    while low<high:
        mid=(low+high)//2
        if nums[mid]<target:
            low=mid+1
        else:
            high=mid
            pos=mid
    return pos
def increase_lis(l,res):
    n=len(l)
    temp=[10**10]*n
    temp[0]=l[0]
    res+=[1]
    for i in range(1,n):
        pos=get_index(temp,l[i])
        res+=[pos+1]
        temp[pos]=l[i]
    return res
while True:
    try:
        n=int(input())
        a=list(map(int,input().strip().split()))
        dp_1,dp_2=[],[]
        dp_1=increase_lis(a,dp_1)
        new_list=a[::-1]
        dp_2=increase_lis(new_list,dp_2)
        maxValue=max([dp_1[i]+dp_2[n-i-1] for i in range(n)])
        print(n-maxValue+1)
    except:
        break

发表于 2018-07-11 10:01:05 回复(1)
# 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

发表于 今天 15:15:45 回复(0)
动态规划;(动态规划之最长上升子序列的引用与改进)
最少几个同学出列==最多几个同学留下来
i从左边开始,求最长上升子序列inc
j从右边开始,求最长下降子序列dec;
相当于每个元素都有自己的左边最长上升子序列和右边的最长下降子序列,
inc[i] + dec[i]相加扣除重复计算自身的1就是留下的最长合法序列;
最少多少个同学出列的结果就是v.size()减最长合法序列;
int main() {
	int n, x, max_i, max_d, max;
	while (cin >> n) {
		vector<int> v, inc(n, 0), dec(n, 0);
		max = 0;
		while (n--) {
			cin >> x;
			v.push_back(x);
		}
		for (int i = 0, j = v.size() - 1; i < v.size(), j >= 0; i++, j--) {
			max_i = 0, max_d = 0;
			for (int k = 0; k < i; k++) {
				if (v[i] > v[k]) {
					if (inc[k] > max_i)max_i = inc[k];
				}
			}
			inc[i] = max_i + 1;
			for (int l = v.size() - 1; l > j; l--) {
				if (v[j] > v[l]) {
					if (dec[l] > max_d)max_d = dec[l];
				}
			}
			dec[j] = max_d + 1;
		}
		for (int i = 0; i < v.size(); i++) {
			if (inc[i] + dec[i] > max) {
				max = inc[i] + dec[i];
			}
		}
		cout << v.size()-(max-1) << endl;
	}
	return 0;
}

发表于 2020-02-23 14:12:39 回复(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)
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

typedef struct{
    int val;
    int subLen;
    int rsubLen;
}SubV;

void cal(vector<SubV> &intarr, bool reverse)
{
    if(reverse) {
        vector<SubV>::reverse_iterator iter, iter1;
        for(iter=intarr.rbegin(); iter!=intarr.rend(); iter++) {
            int max=0;
            for(iter1=intarr.rbegin(); iter1!=iter; iter1++) {    //获取iter左边的最大字串长度
                if(iter1->rsubLen>max && iter1->val<iter->val) 
                    max = iter1->rsubLen;
            }
            iter->rsubLen += max;
            //cout<<iter->val<<"-"<<iter->rsubLen<<" ";
        }
        
    } else {
        vector<SubV>::iterator iter, iter1;
        for(iter=intarr.begin(); iter!=intarr.end(); iter++) {
            int max=0;
            for(iter1=intarr.begin(); iter1!=iter; iter1++) {    //获取iter左边的最大字串长度
                if(iter1->subLen>max && iter1->val<iter->val) 
                    max = iter1->subLen;
            }
            iter->subLen += max;
            //cout<<iter->val<<"-"<<iter->subLen<<" ";
        }
    }
    //cout<<endl;
}

int main()
{
    int n;
    int val;
    
    while(cin>>n) {
        vector<SubV> intarr;
        
        for(int i=0; i!=n; i++) {
            cin>>val;
            
            SubV s;
            s.val = val;
            s.subLen = 1;
            s.rsubLen = 1;
            
            intarr.push_back(s);
        }
        
        cal(intarr, false);    //计算正向递增子串长度
        cal(intarr, true);     //计算逆向递增子串长度
        
        int max=0;
        for(auto sv:intarr) {
            int len = sv.subLen+sv.rsubLen-1;    //双向递增字串长度求和减1
            //cout <<sv.val<<"-"<<len<<" ";    
            if(len > max)
                max = len;
        }
        
        cout<<n-max<<endl;
    }
    
}
发表于 2019-08-08 11:37:24 回复(0)