forked from EndlessCheng/codeforces-go
-
Notifications
You must be signed in to change notification settings - Fork 0
/
1012C.go
61 lines (56 loc) · 1.33 KB
/
1012C.go
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
package main
import (
"bufio"
. "fmt"
"io"
)
// github.com/EndlessCheng/codeforces-go
func CF1012C(_r io.Reader, _w io.Writer) {
in := bufio.NewReader(_r)
out := bufio.NewWriter(_w)
defer out.Flush()
min := func(a, b int) int {
if a < b {
return a
}
return b
}
max := func(a, b int) int {
if a > b {
return a
}
return b
}
var n int
Fscan(in, &n)
a := make([]int, n+2)
for i := 1; i <= n; i++ {
Fscan(in, &a[i])
}
m := (n + 1) / 2
// dp[i][j][0/1] 表示前 i 个元素组成 j 个山峰的答案,0 表示不修改 a[i],1 表示修改 a[i] 使其能够让 a[i+1] 成为山峰
// 转移的时候只需考虑是否修改当前元素,不考虑是否让当前元素成为山峰
dp := make([][][2]int, n+1)
for i := range dp {
dp[i] = make([][2]int, m+1)
for j := 1; j <= m; j++ {
dp[i][j] = [2]int{1e9, 1e9}
}
}
for i := 1; i <= n; i++ {
cost := max(a[i]-a[i+1]+1, 0)
dp[i][0][1] = cost
for j := 1; j <= m; j++ {
dp[i][j][0] = dp[i-1][j][0]
dp[i][j][1] = dp[i-1][j][0] + cost
if i > 1 {
dp[i][j][0] = min(dp[i][j][0], dp[i-2][j-1][1]+max(a[i]-a[i-1]+1, 0))
dp[i][j][1] = min(dp[i][j][1], dp[i-2][j-1][1]+max(a[i]-min(a[i-1], a[i+1])+1, 0))
}
}
}
for k := 1; k <= m; k++ {
Fprint(out, min(dp[n][k][0], dp[n-1][k-1][1]), " ")
}
}
//func main() { CF1012C(os.Stdin, os.Stdout) }