首页 > 试题广场 >

合唱队

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

N 位同学站成一排,音乐老师要请最少的同学出列,使得剩下的 K 位同学排成合唱队形。

K位同学从左到右依次编号为 1,2…,K ,他们的身高分别为 ,若存在 使得,则称这K名同学排成了合唱队形。
通俗来说,能找到一个同学,他的两边的同学身高都依次严格降低的队形就是合唱队形。
例子:
123 124 125 123 121 是一个合唱队形
123 123 124 122不是合唱队形,因为前两名同学身高相等,不符合要求
123 122 121 122不是合唱队形,因为找不到一个同学,他的两侧同学身高递减。


你的任务是,已知所有N位同学的身高,计算最少需要几位同学出列,可以使得剩下的同学排成合唱队形。

注意:不允许改变队列元素的先后顺序 不要求最高同学左右人数必须相等

数据范围:


输入描述:

用例两行数据,第一行是同学的总数 N ,第二行是 N 位同学的身高,以空格隔开



输出描述:

最少需要几位同学出列

示例1

输入

8
186 186 150 200 160 130 197 200

输出

4

说明

由于不允许改变队列元素的先后顺序,所以最终剩下的队列应该为186 200 160 130或150 200 160 130           

用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)
readline();
let input = readline();
let a = input.split(' ').map(x => parseInt(x));
function c(a) {
  //p[i]:i元素左边的最大递增序列长度
  //q[i]:i元素右边的最大递减序列长度
  let p = [0], q = [];
  q[a.length - 1] = 0;
  for (let i = 1; i < a.length; i++) {
    let max = -1;
    //第i个元素的p值等于 {k| k<i&&a[k]<a[i]}的最大p值+1
    for (let j = 0; j < i; j++) {
      if (a[i] > a[j] && max < p[j]) {
        max = p[j];
      }
    }
    p[i] = max + 1;
  }

  for (let i = a.length - 2; i >= 0; i--) {
    let max = -1;
    //第i个元素的q值等于 {k| k>i&&a[k]<a[i]}的最大q值+1
    for (let j = a.length - 1; j > i; j--) {
      if (a[i] > a[j] && max < q[j]) {
        max = q[j];
      }
    }
    q[i] = max + 1;
  }
  //剩余最大人数
  let max = 0;
  for (let i = 0; i < a.length; i++) {
    max = Math.max(p[i] + q[i] + 1, max);
  }
  //最小出列人数
  return (a.length - max);
}
console.log(c(a));

发表于 2022-07-04 00:59:46 回复(0)
  1. 动态规划:时间复杂度O(n^2)
    #include <stdio.h>
    #include <string.h>
    
    int main(){
        int N;scanf("%d",&N);
        int a[N];int max;
        for(int i=0;i<N;i++){
            scanf("%d",&a[i]);
        }
        //逆序遍历,以当前元素为基准,记录其右边的最大严格递减序列的元素个数
        int dp_r[N];memset(dp_r,0,sizeof(dp_r));
        for(int i=N-2;i>-1;i--){
            max=-1;
            for(int j=i+1;j<N;j++){
                if(a[i]>a[j] && dp_r[j]>max){
                    max=dp_r[j];
                    dp_r[i]=dp_r[j]+1;
                }
            }
        }
        //顺序遍历,以当前元素为基准,记录其左边的最大严格递增序列的元素个数
        int dp_l[N];memset(dp_l,0,sizeof(dp_l));
        for(int i=1;i<N;i++){
            max=-1;
            for(int j=i-1;j>-1;j--){
                if(a[i]>a[j] && dp_l[j]>max){
                    max=dp_l[j];
                    dp_l[i]=dp_l[j]+1;
                }
            }
        }
        //遍历整个数组,计算当前元素dp_r[i]+dp_l[i]的大小,计算最大值
        for(int i=0;i<N;i++){
            if(dp_r[i]+dp_l[i]>max){
                max=dp_r[i]+dp_l[i];
            }
        }
        printf("%d",N-max-1);
    }
  2. 建立辅助数组,维持辅助数组元素有序排列,用二分查找找到原数组元素在该辅助数组中该插入的位置,该位置即为动态规划中dp[i]的值,时间复杂度O(nlogn)
    #include <stdio.h>
    #include <string.h>
    
    int search(int* a,int key,int high){//二分查找
        int low=0,mid;
        while(low<=high){
            mid=(low+high)/2;
            if(a[mid]==key){
                return mid;
            }
            else if(a[mid]>key){
                high=mid-1;
            }
            else{
                low=mid+1;
            }
        }
        if(a[mid]>key){
            return mid;
        }
        else{
            return mid+1;
        }
    }
    
    int main(){
        int N;scanf("%d",&N);
        int a[N];int b[N];memset(b,0,sizeof(b));//辅助数组
        for(int i=0;i<N;i++){
            scanf("%d",&a[i]);
        }
        int max=0;int p;
        //顺序遍历,以当前元素为基准,记录其左边的最大严格递增序列的元素个数
        int dp_l[N];dp_l[0]=0;
        b[max]=b[0]=a[0];
        for(int i=1;i<N;i++){
            if(a[i]<=b[0]){//原数组元素值超过辅助数组下界就替换
                dp_l[i]=0;
                b[0]=a[i];
            }
            else if(a[i]>b[max]){//原数组元素值超过辅助数组上界,将其插入后形成新的上界
                dp_l[i]=++max;
                b[max]=a[i];
            }
            else{//原数组元素值在中间就在辅助数组中查找刚好大于它的数并替换
                p=search(b,a[i],max);
                dp_l[i]=p;
                b[p]=a[i];
            }
        }
        max=0;
        //逆序遍历,以当前元素为基准,记录其右边的最大严格递减序列的元素个数
        int dp_r[N];dp_r[N-1]=0;memset(b,0,sizeof(b));
        b[max]=b[0]=a[N-1];
        for(int i=N-2;i>-1;i--){
            if(a[i]<=b[0]){//原数组元素值超过辅助数组下界就替换
                dp_r[i]=0;
                b[0]=a[i];
            }
            else if(a[i]>b[max]){//原数组元素值超过辅助数组上界,将其插入后形成新的上界
                dp_r[i]=++max;
                b[max]=a[i];
            }
            else{//原数组元素值在中间就在辅助数组中查找刚好大于它的数并替换
                p=search(b,a[i],max);
                dp_r[i]=p;
                b[p]=a[i];
            }
        }    
        //遍历整个数组,计算当前元素dp_r[i]+dp_l[i]的大小,计算最大值
        for(int i=0;i<N;i++){
            if(dp_r[i]+dp_l[i]>max){
                max=dp_r[i]+dp_l[i];
            }
        }
        printf("%d",N-max-1);
    }

发表于 2022-06-08 16:43:53 回复(0)
终于弄懂了!!!
#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
using namespace std;
int num;
int height_s;
int deal(vector<int>&height,int num)
{
    vector<int>dp1(num,0);//dp1[i]表示在确定必须选择height[i]的情况下,从左到右身高的最长递增子序列的长度
    //递推公式 if(height[i]>height[j]) dp1[i]=max(dp1[i],dp1[j]+1);
    //初始化 :自己本身长度为1
    //遍历顺序:从前往后
    vector<int>dp2(num, 0);
    for (int i = 0; i < num; i++)dp1[i] = 1;
    for (int i = 0; i < num; i++)dp2[i] = 1;

    for (int i = 0; i < num; i++)
    {
        for (int j = 0; j < i; j++)
        {
            if (height[i] > height[j])
                dp1[i] = max(dp1[i], dp1[j] + 1);
        }
    }
    for (int i = num - 1; i >= 0; i--)
    {
            for (int j = num - 1; j>i; j--)
            {
                if (height[i] > height[j])
                    dp2[i] = max(dp2[i], dp2[j] + 1);
            }
    }
    int maxLength = 0;
    for (int i = 0; i < num; ++i) {
        if (maxLength < dp1[i] + dp2[i] - 1) {
            maxLength = dp1[i] + dp2[i] - 1;
        }
    }
    cout << num - maxLength <<endl;
    return maxLength;
}
int main()
{
    while (cin >> num)
    {
        vector<int>height;
        for (int i = 0; i < num; i++)
        { 
            cin >> height_s;
            height.push_back(height_s);
        }
        deal(height,num);
    }
    return 0;
}


发表于 2022-03-30 11:18:08 回复(1)
while True:
    try:
        n = int(input())
        s = list(map(int,input().split()))
        
        lp=[0]*n
        lq=[0]*n
        for i in range(n):
            if i==0:
                lp[i]=0
            else:
                for j in range(i):
                    if s[i]>s[j]:
                        lp[i]=max(lp[i],lp[j]+1)
        s=s[::-1]
        for i in range(n):
            if i==0:
                lq[i]=0
            else:
                for j in range(i):
                    if s[i]>s[j]:
                        lq[i]=max(lq[i],lq[j]+1)
        lq=lq[::-1]
        re=[]
        for i in range(n):
            re.append(lp[i]+lq[i]+1)
        print(n-max(re))
    except:
        break
理论上应该这么算,就是Python容易超时
发表于 2021-12-16 20:54:18 回复(0)
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)
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)
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)
给定了一个数字列表,从左往右和从右往左,只需要找那一个数左侧和右侧,小于他的有效个数。比如如果是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)
# 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)
#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)
求每个数字在最大递增子串中的位置。

编辑于 2019-07-25 23:36:06 回复(0)
// 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)
#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)
我就说两点
1 这里要循环
2 每次计算完的vector要clear或者声明为局部变量
发表于 2017-09-07 17:04:03 回复(1)
最长递增子序列
#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)