-
-
Notifications
You must be signed in to change notification settings - Fork 300
/
964.cpp
86 lines (82 loc) · 2.7 KB
/
964.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
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
__________________________________________________________________________________________________
sample 4 ms submission
class Solution {
public:
int leastOpsExpressTarget(int x, int target) {
int pos = 0, neg = 0, exp = 0;
while (target) {
int cur = target%x;
target /= x;
if (exp) {
int tmpPos = min(cur*exp+pos, (cur+1)*exp+neg);
int tmpNeg = min((x-cur)*exp+pos, (x-cur-1)*exp+neg);
pos = tmpPos;
neg = tmpNeg;
} else {
pos = cur * 2;
neg = (x-cur) * 2;
}
exp++;
}
return min(pos, exp+neg) - 1;
}
};
__________________________________________________________________________________________________
sample 9184 kb submission
int dp[30][2];
int GetCnt(int v) {
if (v == 0) return 1;
else return v - 1;
}
class Solution {
void Update(int i, int j, int v) {
if (dp[i][j] == -1 || dp[i][j] > v) dp[i][j] = v;
}
public:
int leastOpsExpressTarget(int x, int target) {
memset(dp, -1, sizeof(dp));
int val[30], cnt = 0;
while (target) {
val[cnt++] = target % x;
target /= x;
}
val[cnt++] = 0;
//for (int i = 0; i < cnt; i++) cout << val[i] << " "; cout << endl;
dp[cnt - 1][0] = 0;
dp[cnt - 1][1] = GetCnt(cnt - 1);
for (int i = cnt - 2; i >= 0; i--) {
int v = val[i];
// -
for (int j = i + 1; j < cnt; j++) {
// no left
if (dp[j][1] != -1)
{
Update(i, 0, dp[j][1] + (x - v) * (GetCnt(i) + 1));
}
// left
if (dp[j][1] != -1 && v != x - 1)
{
Update(i, 1, dp[j][1] + (x - v - 1) * (GetCnt(i) + 1));
}
if (val[j] != x - 1)break;
}
// +
// no left
if (dp[i + 1][0] != -1)
{
if (v == 0) {
Update(i, 0, dp[i + 1][0]);
} else {
Update(i, 0, dp[i + 1][0] + v * (GetCnt(i) + 1) + (i == cnt - 2 ? -1 : 0));
}
}
// left
if (v < x - 1 && dp[i + 1][0] != -1) {
Update(i, 1, dp[i + 1][0] + (v + 1) * (GetCnt(i) + 1) + (i == cnt - 2 ? -1 : 0));
}
}
//for (int i = 0; i < cnt; i++) printf("%d %d\n", dp[i][0], dp[i][1]);
return dp[0][0];
}
};
__________________________________________________________________________________________________