思路
木棒的可能长度区间是 $[max(w_i), sum(w_i)]$,其中 $w_i$ 是第 $i$ 根木棍长度。
从小到大枚举这些长度,检验能否将所有木棍拼接成若干根等长木棒,第一次找到的木棒长度就是答案。
剪枝:
- 木棒长度必须是所有木棍长度之和的约数。
- 优先使用长度更大的木棍拼接木棒,则总剩余长度更小,可以尽早排除非法情况。这样操作并不影响正确性,因为对于任意一组合法方案,将每根木棒使用的木棍按长度降序排列,再将所有木棒按使用的最长木棍降序排列(第一根最长排前面,第一根长度相等,则第二根更长排前面,以此类推),都可转换成优先使用长度更大的木棍拼接木棒的方案。
- 如果当前木棒使用了第 $i$ 根木棍,则下一次枚举直接从 $i$ 之后开始,因为之前的木棍要么已被使用,要么拼接到当前木棒后导致方案非法,而一根木棍如果无法放到当前木棒的前面位置,则也无法放到当前木棒的后面位置。因为只要它可以放到后面位置,则将它交换到前面位置也是合法方案。或者说同一根木棒内部是木棍长度的组合,而不是排列,因此可以规定一种排列顺序消除冗余。
- 如果未使用的最长的一根长度为 $w[i]$ 的木棍拼接当前木棒无法成功,则相同长度的其它木棍也无法拼接到当前木棒。因为如果相同长度的其它木棍可以拼接到当前木棒,由于剪枝 $3$,$w[i]$ 会拼接到后续木棒,由于长度相同,把 $w[i]$ 交换回来,将后续木棒内部按木棍下标排序,就可推出当前方案合法。
- 如果 $w[i]$ 拼到当前木棒开头导致无法成功,则 $w[i]$ 无法放到任何一根木棒。原因是:由于剪枝 $3$,$w[i]$ 不会放到当前木棒,只会放到后续木棒开头。将那根木棒与当前木棒交换,也是合法方案。
- 如果 $w[i]$ 刚好能拼到当前木棒结尾,但后续木棒无法拼接成功,则 $w[i]$ 无法放到任何一根木棒。原因是:若 $w[i]$ 可以放到其它木棒,则把它交换到当前木棒结尾等长区域,再将那根木棒按木棍下标排序,也是合法方案。
package main
import (
"bufio"
"sort"
"fmt"
"os"
)
const N = 100
var (
rd = bufio.NewReader(os.Stdin)
wt = bufio.NewWriter(os.Stdout)
n int
w [N]int
st [N]bool
sum int
lth int
)
func dfs(u, cur, start int) bool {
if u * lth == sum {
return true
}
if cur == lth {
return dfs(u + 1, 0, n - 1)
}
for i := start; i >= 0; i-- {
if st[i] {
continue
}
clth := cur + w[i]
if clth <= lth {
st[i] = true
ret := dfs(u, clth, i - 1)
st[i] = false
if ret {
return ret
}
}
if cur == 0 || clth == lth {
return false
}
j := i - 1
for j >= 0 && w[j] == w[i] {
j--
}
i = j + 1
}
return false
}
func main() {
defer wt.Flush()
for true {
fmt.Fscanln(rd, &n)
if n == 0 {
break
}
sum = 0
for i := 0; i < n; i++ {
fmt.Fscan(rd, &w[i])
sum += w[i]
}
fmt.Fscanln(rd)
sort.Ints(w[:n])
lth = w[n - 1]
for true {
if sum % lth == 0 && dfs(0, 0, n - 1) {
fmt.Fprintln(wt, lth)
break
}
lth++
}
}
}
这道题数据好严啊,只有一个数据测试点,很难混测试点,要么满分,要么一份没有,QAQ
不是我这水平能做出来的题
考试肯定会给小数据,剪枝想不到就算了,我也想不到,先学会暴力枚举
嗯嗯