技术学习分享_CKX技术 技术资讯 #yyds干货盘点# 动态规划专题:合唱队形

#yyds干货盘点# 动态规划专题:合唱队形

广告位

1.简述:

描述

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

合唱队形是指这样的一种队形:设K位同学从左到右依次编号为 1,2…,K,他们的身高分别为 T1,T2,…,TK,  则他们的身高满足 #yyds干货盘点# 动态规划专题:合唱队形

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

数据范围: #yyds干货盘点# 动态规划专题:合唱队形 ,身高满足 #yyds干货盘点# 动态规划专题:合唱队形

输入描述:

第一行输入一个正整数 n 表示同学的总数。

第二行有 n 个整数,用空格分隔,第 i 个整数 ti 是第 i 位同学的身高(厘米)。

输出描述:

输出仅有一个整数,即最少需要几个同学出列

示例1

输入:

8
186 186 150 200 160 130 197 220

输出:

4

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);
}
}
}
本文来自网络,不代表技术学习分享_CKX技术立场,转载请注明出处。

作者: CKX技术

上一篇
下一篇
广告位

发表回复

返回顶部