2147 . 哈卡雜貨店

Submit
Status
Discussion / Solution
Ranklist
Back to Problems List

TopCoder

thtsshz
Things not worth doing are not worth doing well.

User's AC Ratio

73.7% (28/38)

Submission's AC Ratio

42.5% (51/120)

Tags

CKsim 2019-CKsim

Description

哈卡雜貨店裡，只有一排貨架，擺放著各式商品。然而裡頭的哈卡老闆有強迫症，他想要讓這個貨架的商品價格，從商品編號1~N，至少有K件商品價格是按序遞增的。哈卡是不會調降價錢的，哈卡也想把力氣省下來，哈卡決定以某件商品加一元的方式，直到貨架上的商品有至少K個按序遞增。

試問哈卡最少需要做幾次“加某件商品一元”這個動作，才能讓貨架上的N件商品至少有K件的價格按序遞增？

以上題敘的意思也就是：
給你一個長度為N的序列，你可以對任一項加一，求最少要加幾次才存在一個子序列長度為K，且值非嚴格遞增。(子序列是不用連續的)

Input Format

輸入兩個數字N, K，代表貨架上的商品數以及要求的遞增子序列長度。（不必嚴格遞增）
下一行按序輸入N個數字$ a_{i}$代表商品 i 的價格。
$(1 \leq N \leq 200, 1 \leq K \leq N , 1\leq a_i \leq 1000000000)$

Output Format

輸出最少需要幾次加一元的動作，才能符合哈卡期望。

Sample Input 1

5 4
1 5 10 7 6

Sample Output 1

1

Sample Input 2

10 5
10 9 8 7 6 5 4 3 2 1

Sample Output 2

10

Sample Input 3

2 1
5 10

Sample Output 3

0

Hints

Problem Source

Problem Set by jeeeerrrpop

Subtasks

No. Testdata Range Constraints Score
1 0~4 $N=K$ 7
2 5~9 $N \leq 40$ 21
3 10~14 $a_i \leq 200$ 21
4 15~19 無特殊限制 51

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 1000 262144 65536 1
1 1000 262144 65536 1
2 1000 262144 65536 1
3 1000 262144 65536 1
4 1000 262144 65536 1
5 1000 262144 65536 2
6 1000 262144 65536 2
7 1000 262144 65536 2
8 1000 262144 65536 2
9 1000 262144 65536 2
10 1000 262144 65536 3
11 1000 262144 65536 3
12 1000 262144 65536 3
13 1000 262144 65536 3
14 1000 262144 65536 3
15 1000 262144 65536 4
16 1000 262144 65536 4
17 1000 262144 65536 4
18 1000 262144 65536 4
19 1000 262144 65536 4
Submit
Back to Top