# 2023 mock interview Candidate: louis
###### tags: `Tag(template)`
---
https://codeforces.com/problemset/problem/1748/C

<font size= 4><center> **倒數計時** </center></font>
<iframe id="oak-embed" width="700" height="400" style="display: block; margin: 0px auto; border: 0px;" src="http://zbryikt.github.io/quick-timer"></iframe>

# 題目講解
//time: 21:37

the score of array is means
sum(a1 + a2 + a3 ...) = 0

5
0 1 2 3 4
2 0 1 -1 0

idx: 1 value: 0 -> -2

2 -2 1 -1 0
2 0 1 0 0

the score = 3

score is prefix, maximum the zero nubmer
replace 0 to any int

# 作法講解
//time: 21

2 0 1 -1 0
2 2 3 2 2

choose index = 4
2 0 1 -1 -2
2 2 3 2 0

choose index = 1
2 0 1 -1 -2
2 2 3 2 0
-2 -2 -2 -2

observation:
we must choose smallest index to replace

idea:
greedy, we do from to left to right
when we meet 0, we just calculate the current
add a negative sign

x v
2 0 1 -1 0 x x x
2 2 3 2 -2 0 0 0

what if we meet 0, we can either replace to current -value, or skip it
TC: O(n2^n)

x v
2 0 1 -1 0 x x x
2 2 3 2 -2 0 0 0

change or no change

dp[i][0], maximum score can get, start from index i, and idnex is not changed
dp[i][1], maximum score can get, start from index i, and idnex changed

i -> i+1, value change 2
dfs(i, pre, ischanged)

int score = pre == 0;
res = dfs(i+1, pre+arr[i], 0)
if arr[i] == 0
res = dfs(i+1, 0, 1)

val = 2 0 1 -1 1 -1 1 -1
sum 2 2 3 2 3 2 3 2

val = 2 -2 1 -1 1 -1 1 -1
sum 2 0 1 0 3 2 3 2

val = 2 0 2 1 1 -1 1 -1 1 -1
sum 2 2 4 5 6 5 6 5 6 5

sum 2 0 2 3 4 3 4 3 4 3

val = 2 -5 2 1 1 -1 1 -1 1 -1
sum 2 2 4 5 6 5 6 5 6 5

dp[i][current sum] space is very big

v v
2 0 | 1 -1 0 | z z z z 0
2 2 3 2 2
x x x x x x x x x
y y y y y y

v v
2 0 | 1 -1 0 | z z z z 0
2 2 3 2 2

x v
2 0 x x x 0 0 0 z z z z 0
2 -2 a a a 0 0 2
x x

x v
2 0 x x x | 0 0 0 z z z z 0
2 0 a a a | 0 0 2
x x

x v
2 2 x x x | -2 0 0 z z z z 0
2 0 a a a | 0 0 2
x x

step 1: change first idx value is 0
step 2: change second idx, value is 0,

0 x x x | (0 y y y) | (0 z z z)
pre= 2 2 0 0 0
0

either change or no change -> find maximum score before next zero index

0 x x x | (0 y y y) | (0 z z z)
pre= 2 2 0 0 0
0

v
2 0 0 0 | 0 0 0 0 0 0| (0 z z z)
pre= 2 2 2 [0 0 0 0 0 0 0]

v
2 [-2] | 0 0 0 0 0 0| (0 z z z)
pre= 2 0 2 [0 0 0 0 0 0 0]

0 x x x | (0 y y y) | (0 z z z)
pre= 2 -2 y y y

2 0 2 -1 1 -1
2 2 4 3 4 3

2 -2 2 -1 1 -1
2 0 2 1 2 1

2 0 3 -3 3 -3
2 0 3 0 3. 0
-2 1 -2 1 -2

how to find the affect of replace??

seperately do each segment

hashtable record the number, value -> fre

change:
0
-2, max of (mp[2], mp[3], mp[4])

0 -> -3
0 -> -4

0 -> 2
0 -> 3

3 0 3 -3 3 -3 |
3 -3 3 0 3. 0
0 -3 0 -3

1
2 0 |x x x x x x| 0 | |
p

0
4 -4 | x x x x x x x x |
5 -5 | x+1 x+1 x+1 x+1 x+1 x+1 x+1 x+1 |
6 -6 | x+2 x+2 x+2 x+2 x+2 x+2 x+2 x+2 |
2 -2
0

no change
mp[0]

use the value to calculate the next segment

hint: we can think which range is chagned after replace 0 to anther value.

# coding
//time:

# 完成
//time:

# comment

self:
列舉example greedy觀察失敗
然後想了brute force複雜度很高
然後想了dp但沒想到prefix可以變成其他數值gg, wrong
開始卡 -> how to avoid? ask for a hint