-
Notifications
You must be signed in to change notification settings - Fork 492
/
d.go
48 lines (47 loc) · 831 Bytes
/
d.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
package main
// github.com/EndlessCheng/codeforces-go
func connectTwoGroups(cost [][]int) (ans int) {
n, m := len(cost), len(cost[0])
min := func(a, b int) int {
if a < b {
return a
}
return b
}
mi := append([]int(nil), cost[0]...)
for _, row := range cost[1:] {
for j, v := range row {
mi[j] = min(mi[j], v)
}
}
dp := make([][]int, n)
for i := range dp {
dp[i] = make([]int, 1<<m)
for j := range dp[i] {
dp[i][j] = -1
}
}
var f func(int, int) int
f = func(p, conn int) (res int) {
if p == n {
for i, v := range mi {
if conn>>i&1 == 0 {
res += v
}
}
return
}
dv := &dp[p][conn]
if *dv != -1 {
return *dv
}
defer func() { *dv = res }()
res = 1e9
for i, v := range cost[p] {
res = min(res, v+f(p+1, conn|1<<i))
}
return
}
ans = f(0, 0)
return
}