N 位同学站成一排，音乐老师要请最少的同学出列，使得剩下的 K 位同学排成合唱队形。
用例两行数据，第一行是同学的总数 N ，第二行是 N 位同学的身高h[i]，以空格隔开
数据范围：，
最少需要几位同学出列
8 186 186 150 200 160 130 197 200
4
由于不允许改变队列元素的先后顺序，所以最终剩下的队列应该为186 200 160 130或150 200 160 130
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容易超时
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);
}
}
} 
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)
} 
#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;
}
//两边递增子序列，每次二分查找插入
#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;
} # 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
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);
}
}
} 
// 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; }
}
#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;
} 
#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;
}
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);
}
}
最长递增子序列
#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;
} 
#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;
} 
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();
}
}
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);
}
}
}
//动态规划 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; } }
扫描二维码，关注牛客网
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
京公网安备
11010502036488号
