哈卡雜貨店裡,只有一排貨架,擺放著各式商品。然而裡頭的哈卡老闆有強迫症,他想要讓這個貨架的商品價格,從商品編號1~N,至少有K件商品價格是按序遞增的。哈卡是不會調降價錢的,哈卡也想把力氣省下來,哈卡決定以某件商品加一元的方式,直到貨架上的商品有至少K個按序遞增。
試問哈卡最少需要做幾次“加某件商品一元”這個動作,才能讓貨架上的N件商品至少有K件的價格按序遞增?
以上題敘的意思也就是:
給你一個長度為N的序列,你可以對任一項加一,求最少要加幾次才存在一個子序列長度為K,且值非嚴格遞增。(子序列是不用連續的)
輸入兩個數字N, K,代表貨架上的商品數以及要求的遞增子序列長度。(不必嚴格遞增)
下一行按序輸入N個數字$ a_{i}$代表商品 i 的價格。
$(1 \leq N \leq 200, 1 \leq K \leq N , 1\leq a_i \leq 1000000000)$
輸出最少需要幾次加一元的動作,才能符合哈卡期望。
Problem Set by jeeeerrrpop
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 |