AcWing 482. 合唱队形
原题链接
中等
作者:
暂时换个名字
,
2021-01-27 19:09:24
,
所有人可见
,
阅读 337
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();int[] arr = new int[n];
for(int i=0;i<n;i++)arr[i]=sc.nextInt();
dp(arr);
}
public static void dp(int[] arr) {
int res=0;
for(int i=0;i<arr.length;i++) {
int temp=lis(arr,i)+downLis(arr,i)-1;
res=Math.max(res, temp);
}
System.out.println(arr.length-res);
}
public static int lis(int[] arr,int k) {
int[] biao=new int[arr.length];
for(int i=0;i<=k;i++) {
biao[i]=1;
for(int j=0;j<i;j++) {
if(arr[j]<arr[i]&&biao[j]+1>biao[i])biao[i]=biao[j]+1;
}
}
return biao[k];//第k个数是一定要被选的
}
public static int downLis(int[] arr,int k) {
int[] biao = new int[arr.length];
for(int i=arr.length-1;i>=k;i--) {
biao[i]=1;
for(int j=arr.length-1;j>i;j--) {
if(arr[j]<arr[i]&&biao[j]+1>biao[i])biao[i]=biao[j]+1;
}
}
return biao[k];
}
}