/
818.cpp
66 lines (63 loc) · 2.02 KB
/
818.cpp
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
64
65
66
__________________________________________________________________________________________________
sample 4 ms submission
class Solution {
public:
int racecar(int target) {
// pos[i] = 2^(i)-1
// pos[i] - pos[i-1] = 2^(i) > pos[i-1]
vector<int> dp(target * 2, -1);
dp[0] = 0;
return impl(target, dp);
}
static int impl(int target, vector<int>& dp) {
assert(target < dp.size() && target >= 0);
if (dp[target] > 0) {
return dp[target];
}
int steps = log2(target + 1);
int start = pow(2, steps) - 1;
int ret = 0;
if (start == target) {
// nothing
} else {
assert(start < target);
int end = pow(2, steps + 1) - 1;
ret = impl(end - target, dp) + 2; // AR
for (int i = 0; i < steps; ++i) {
auto tmp = impl(target - start + pow(2, i) - 1, dp) + 2 + i; // RA...AR
ret = min(ret, tmp);
}
}
dp[target] = ret + steps;
return dp[target];
}
};
__________________________________________________________________________________________________
sample 8568 kb submission
constexpr int kMaxT = 10000;
int m[kMaxT + 1][2]={0};
class Solution {
public:
int racecar(int target) {
if (m[1][0] == 0) {
for (int t = 1; t <= kMaxT; ++t) {
const int n = ceil(log2(t + 1));
if (1 << n == t + 1) {
m[t][0] = n;
m[t][1] = n + 1;
continue;
}
const int l = (1 << n) - 1 - t;
m[t][0] = n + 1 + min(m[l][1], m[l][0] + 1);
m[t][1] = n + 1 + min(m[l][0], m[l][1] + 1);
for (int i = 1; i < t; ++i) {
const int mi = min(m[i][0] + 2, m[i][1] + 1);
m[t][0] = min(m[t][0], m[t - i][0] + mi);
m[t][1] = min(m[t][1], m[t - i][1] + mi);
}
}
}
return min(m[target][0], m[target][1]);
}
};
__________________________________________________________________________________________________