哈卡雜貨店裡，只有一排貨架，擺放著各式商品。然而裡頭的哈卡老闆有強迫症，他想要讓這個貨架的商品價格，從商品編號1~N，至少有K件商品價格是按序遞增的。哈卡是不會調降價錢的，哈卡也想把力氣省下來，哈卡決定以某件商品加一元的方式，直到貨架上的商品有至少K個按序遞增。
試問哈卡最少需要做幾次“加某件商品一元”這個動作，才能讓貨架上的N件商品至少有K件的價格按序遞增？
以上題敘的意思也就是：
給你一個長度為N的序列，你可以對任一項加一，求最少要加幾次才存在一個子序列長度為K，且值非嚴格遞增。(子序列是不用連續的)
$K\le N\le 200, a_i\le 10^9$
這題子測資切得蠻好的 所以我應該會分開寫
subtask1: $N=K$
等價於要讓整個序列變得非嚴格遞增
就只要貪心的把當前項加到不小於前面的就好
$\mathcal{O}(N)$
subtask2: $N\le 40$
這筆我不知道要幹嘛 跳過
subtask3: $a_i\le 200$
考慮$dp[K][C][N]$代表以第$N$個為最後一項，目前長度為$K$，且已經把$a_N$弄成$C$了
這樣轉移式就是
$$dp[K][C][N]=\min_{A\le C, B<N} dp[K-1][A][B]+C-a_N (\text{ if } C>a_N)$$
只要透過適當轉移順序 順便紀錄點東西就能做到$\mathcal{O}(1)$轉移
所以複雜度$\mathcal{O}(KNC)$
subtask 4: No other constraints
直接拿subtask3的dp 把序列給離散化後就能變回第三題的樣子 離散化複雜度$O(NlogN)$
整體複雜度$\mathcal{O}(NlogN+KN^2)$
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
|
#include <bits/stdc++.h>
using namespace std;
#define EmiliaMyWife ios::sync_with_stdio(0); cin.tie(NULL);
#define mem(i,j) memset(i,j,sizeof (i));
using ll = int64_t;
using ull = uint64_t;
using ld = long double;
using uint = uint32_t;
const double EPS = 1e-8;
const int INF = 0x3F3F3F3F;
const ll LINF = 4611686018427387903;
const int MOD = 1e9+7;
const int N = 201;
ll dp[N][N][N];
signed main() {
EmiliaMyWife
int n, k;
ll ans = LINF;
cin >> n >> k;
vector<int> arr(n + 1), owo(n);
for(int i = 0; i < n; i++)
cin >> arr[i + 1], owo[i] = arr[i + 1];
for(int i = 0; i < N; i++)
for(int j = 0; j < N; j++)
for(int k = 0; k < N; k++)
dp[i][j][k] = LINF;
sort(owo.begin(), owo.end()); owo.erase(unique(owo.begin(), owo.end()), owo.end());
for(int len = 1; len <= k; len++) {
vector<ll> mn(n + 1, LINF);
if(len == 1)
mn[0] = 0;
for(int j = 0; j < owo.size(); j++) {
for(int i = 1; i <= n; i++) {
if(owo[j] >= arr[i])
dp[i][j][len] = mn[i - 1] + owo[j] - arr[i];
mn[i] = min({mn[i], mn[i - 1], dp[i][j][len - 1]});
if(len == k)
ans = min(ans, dp[i][j][len]);
}
}
}
cout << ans << '\n';
return 0;
}
|