音乐课上,老师将 位同学排成一排。老师希望在不改变同学相对位置的前提下,从队伍中选出最少数量的同学,使得剩下的同学排成合唱队形。
记合唱队形中一共有 位同学,记编号为 ,第 个人的身高为 。要求:存在一位同学编号为 ,使得 严格递增,且 严格递减;更具体地,合唱队形呈 、 。
你能帮助老师计算,最少需要出列多少位同学,才能使得剩下的同学排成合唱队形?
第一行输入一个整数 代表同学数量。
第二行输入 个整数 代表每一位同学的身高。
输出一个整数,代表最少需要出列的同学数量。
8 186 186 150 200 160 130 197 200
4
在这个样例中,有且仅有两种出列方式,剩下的同学分别为 和 。
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; } }