合唱队__牛客网

Javascript_V8

阿锋.201910102005207

//这里有一个示例需要补充

//8
//1 2 3 1 2 4 5 6

//目前示例没有满足最高不能为头尾

// 左递增，右递减。最高不能为头尾

let n;
function func(height) {
const list = [];
for (let i = 0, l = height.length; i < l; i++) {
list[i] = 1;
for (let j = 0; j <= i; j++) {
if (height[i] > height[j]) {
list[i] = Math.max(list[i], list[j] + 1);
}
}
}
return list;
}
while (n = readline()) {
n = parseInt(n);
let height = readline().split(' ').map(i => parseInt(i));
let list1 = func(height);
let list2 = func(height.reverse()).reverse();
let list3 = list1.map((i, idx) => i + list2[idx]);
let max = 0, idx = -1;
list3.forEach((i, index) => {
if (index !== 0 && index !== list3.length-1 && list1[index]!==1 && list2[index]!==1) {
if (max < i) {
max = i;
idx = index;
}
}
});
//print(max)
//print(list1)
//print(list2)
//print(list3)
console.log(n - (max - 1));
}

发表于 2022-08-31 16:21:41 回复(0)

Javascript_V8

独孤剑走偏锋

动态规划

const N = readline()
const hArr = readline().trim().split(' ').map(i => +i)
const left = []
const right = []
for (let i = 0; i < N; i++) {
    left[i] = right[i] = 1
}
for (let i = 1; i < N; i++) {
    let max = left[i]
    for (let j = i - 1; j >= 0; j--) {
        if (hArr[j] < hArr[i]) {
            max = Math.max(max, left[j] + left[i])
        }
    }
    left[i] = max
}
for (let i = N - 2; i >= 0; i--) {
    let max = right[i]
    for (let j = i + 1; j < N; j++) {
        if (hArr[j] < hArr[i]) {
            max = Math.max(max, right[j] + right[i])
        }
    }
    right[i] = max
}
var res = left.reduce((res, l, i) => {
    return Math.max(res, left[i] + right[i] - 1)
}, 0)
print(N - res)

发表于 2022-07-08 22:53:16 回复(0)

Javascript_V8

阿米诺斯

readline();
let input = readline();
let a = input.split(' ').map(x => parseInt(x));
function c(a) {
  //p[i]:i元素左边的最大递增序列长度
  //q[i]:i元素右边的最大递减序列长度
  let p = [0], q = [];
  q[a.length - 1] = 0;
  for (let i = 1; i < a.length; i++) {
    let max = -1;
    //第i个元素的p值等于 {k| k<i&&a[k]<a[i]}的最大p值+1
    for (let j = 0; j < i; j++) {
      if (a[i] > a[j] && max < p[j]) {
        max = p[j];
      }
    }
    p[i] = max + 1;
  }

  for (let i = a.length - 2; i >= 0; i--) {
    let max = -1;
    //第i个元素的q值等于 {k| k>i&&a[k]<a[i]}的最大q值+1
    for (let j = a.length - 1; j > i; j--) {
      if (a[i] > a[j] && max < q[j]) {
        max = q[j];
      }
    }
    q[i] = max + 1;
  }
  //剩余最大人数
  let max = 0;
  for (let i = 0; i < a.length; i++) {
    max = Math.max(p[i] + q[i] + 1, max);
  }
  //最小出列人数
  return (a.length - max);
}
console.log(c(a));

发表于 2022-07-04 00:59:46 回复(0)

Javascript_V8

不系之舟1027

发表于 2022-03-23 15:39:22 回复(0)

Javascript_V8

牛客589890733号

wdnmd，好家伙，哪位同学的身高为0，真nm

发表于 2021-12-28 19:45:10 回复(0)

合唱队

输入描述:

输出描述:

输入

输出

说明

问题信息

热门推荐

通过挑战的用户

相关试题