#H. 删除最少的元素

    Type: Default 1000ms 256MiB

删除最少的元素

You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

给定有 n 个数的 A 序列:A1,A2,A3AnA_1,A_2,A_3\cdots A_n。对于这个序列,我们想得到一个子序列

Ap1,Ap2ApiApm(1p1<p2<pi<<pmn)A_{p_1}, A_{p_2} \cdots A_{p_i} \cdots A_{p_m}(1 \le p_1 < p_2<\cdots p_i < \cdots < p_m \le n)

满足 Ap1Ap2ApiApmA_{p_1} \ge A_{p_2} \ge \cdots \ge A_{p_i} \le \cdots \le A_{p_m}

从 A 序列最少删除多少元素,可以得到我们想要的子序列。

输入格式

第一行输入一个整数 n,代表 A 序列中数字的个数。 第二个输入 n 个整数,代表A1,A2,A3...AnA_1,A_2,A_3...A_n(1n10001Ai10000(1 \leq n \leq 1000,1 \leq A_i \leq 10000

输出格式

输出需要删除的元素个数,占一行。

样例输入

7
3 2 4 1 2 5 3

样例输出

2

查看提示 提示 可以从前往后做一次最长不升子序列,在从后往前做最长不上升子序列。分别记录从前往后以第 i 个元素为结尾的最长不升子序列长度 dp1[i],和从后往前以第 i 个元素为结尾的最长不升子序列长度 dp2[i]。这样 dp1[i] + dp2[i] - 1 就是得到的 B 序列的长度。

字段和子序列 -- 动态规划

Not Claimed
Status
Done
Problem
8
Open Since
2024-12-13 0:00
Deadline
2024-12-20 23:59
Extension
24 hour(s)