做网站怎样写标题网络游戏推广怎么做

【题目描述】

【思路】
即找到一个k，使得k左边从k到1严格递减，右边从k到n也严格递减。实际上就是两个最长上升子序列问题。

Acwing 482. 合唱队形

import java.io.*;
import java.lang.Math;
public class Main{static int N = 110;public static void main(String args[]) throws Exception{BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));BufferedWriter log = new BufferedWriter(new OutputStreamWriter(System.out));int n = Integer.parseInt(bf.readLine());int [] q =new int[n+ 1];int f[] = new int[n + 1];int g[]= new int[n + 1];String strArr[] = bf.readLine().split(" ");for(int i = 1; i <= n; i++) q[i] = Integer.parseInt(strArr[i - 1]);//T1<…<Ti>Ti+1>…>TK(1≤i≤K)。//f[i]为以i结尾的子序列最长长度for(int i = 1; i <= n; i++){f[i] = 1;for(int j =1; j < i; j++){if( q[i] > q[j]) f[i] = Math.max(f[j] + 1, f[i]);}}for(int i = n; i >= 1; i --){g[i] = 1;for(int j = n; j > i; j --)if(q[j] < q[i] ) g[i] =Math.max(g[j] + 1, g[i]);}int res = 0;//枚举每一个可能的ifor(int i = 1; i <= n; i ++){//队列最多可以有多少个同学res =Math.max(res, f[i] + g[i] - 1);}//最少需要几位同学出列。System.out.println(n - res);}
}