11
#yyds干货盘点# 动态规划专题：合唱队形
source link: https://blog.51cto.com/u_15488507/5805246
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
#yyds干货盘点# 动态规划专题：合唱队形
精选 原创1.简述：
描述
N位同学站成一排，音乐老师要请其中的 (N-K) 位同学出列，使得剩下的K位同学排成合唱队形。
合唱队形是指这样的一种队形：设K位同学从左到右依次编号为 1，2…，K，他们的身高分别为 T1，T2，…，TK， 则他们的身高满足
你的任务是，已知所有 n 位同学的身高，计算最少需要几位同学出列，可以使得剩下的同学排成合唱队形。
数据范围： ，身高满足
输入描述：
第一行输入一个正整数 n 表示同学的总数。
第二行有 n 个整数，用空格分隔，第 i 个整数 ti 是第 i 位同学的身高(厘米)。
输出描述：
输出仅有一个整数，即最少需要几个同学出列
示例1
8
186 186 150 200 160 130 197 220
186 186 150 200 160 130 197 220
2.代码实现：
import java.util.*;
public class Main{
public static void main(String[] args){
Scanner in = new Scanner(System.in);
while(in.hasNext()){
int num = in.nextInt();
int[] nums = new int[num];
for(int i=0;i<num;i++){
nums[i] = in.nextInt();
}
// 连自己 左边 满足条件的最大值
// nums[i] > nums[k] dp[i] = max(dp[i], dp[k] +1);
int[] dp_l = new int[num];
// 右边满足条件的最大值
int[] dp_r = new int[num];
//初始化 左边包括自己 全部设成1
for(int i=0;i<num;i++){
dp_l[i] =1;
}
// 求值
for(int i=1;i<num;i++){
for(int k=0;k<i;k++){
if(nums[i]>nums[k]) dp_l[i] = Math.max(dp_l[i],dp_l[k]+1);
}
}
for(int i=num-2;i>=0;i--){
for(int k=num-1;k>i;k--){
if(nums[i]>nums[k]) dp_r[i] = Math.max(dp_r[i],dp_r[k]+1);
}
}
int max=1;
for(int i=0;i<num;i++){
max = Math.max(max, dp_l[i] + dp_r[i]);
}
System.out.println(num-max);
}
}
}
public class Main{
public static void main(String[] args){
Scanner in = new Scanner(System.in);
while(in.hasNext()){
int num = in.nextInt();
int[] nums = new int[num];
for(int i=0;i<num;i++){
nums[i] = in.nextInt();
}
// 连自己 左边 满足条件的最大值
// nums[i] > nums[k] dp[i] = max(dp[i], dp[k] +1);
int[] dp_l = new int[num];
// 右边满足条件的最大值
int[] dp_r = new int[num];
//初始化 左边包括自己 全部设成1
for(int i=0;i<num;i++){
dp_l[i] =1;
}
// 求值
for(int i=1;i<num;i++){
for(int k=0;k<i;k++){
if(nums[i]>nums[k]) dp_l[i] = Math.max(dp_l[i],dp_l[k]+1);
}
}
for(int i=num-2;i>=0;i--){
for(int k=num-1;k>i;k--){
if(nums[i]>nums[k]) dp_r[i] = Math.max(dp_r[i],dp_r[k]+1);
}
}
int max=1;
for(int i=0;i<num;i++){
max = Math.max(max, dp_l[i] + dp_r[i]);
}
System.out.println(num-max);
}
}
}
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK