本文主要是介绍（2019CSP模拟）DTOJ 4627. 灰烬，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题意
灰烬之地有一排石柱，从左到右共有 n n n 个，其中有一些上面有灰烬，有一些上面没有。
你现在可以操控风的力量，风只能从左到右吹，每次你可以选择一个 k k k ( k k k 每次都可以变化)，扬起前 n − k n-k n−k 个石柱上的一半的灰烬(你可以认为灰烬无穷多，每次取当前的一半，换言之是可以无限复制的)，将其向右吹动 k k k 个位置。
问至少多少次可以使灰烬遍布每一个石柱。无解输出 − 1 -1 −1 。
| 测试点编号 | n n n | ∑ n \sum {n} ∑n |
|---|---|---|
| 1~4 | ≤ 20 \le 20 ≤20 | ≤ 80 \le 80 ≤80 |
| 5~7 | ≤ 32 \le 32 ≤32 | ≤ 120 \le 120 ≤120 |
| 8~10 | ≤ 40 \le 40 ≤40 | ≤ 120 \le 120 ≤120 |
题解
考场上想了半天的状压DP和折半搜索，想把效率减为 O ( 2 n / 2 ) O(2^{n/2}) O(2n/2)，后来感觉状态不会很多，以及极限情况下答案是6，然后随便乱打了一个记忆化的BFS暴力，把map改成哈希表卡了卡常，发现极限挺快的就不管了，然后果然TLE了。
其实在BFS的时候只要搜到答案为5的，如果搜不到答案就是6，以及在转移时直接位运算就可变为 O ( n ) O(n) O(n)，这样效率就变为严格的 O ( n 5 ) O(n^{5}) O(n5)，就很稳了。
反思：
要善于发现题目的性质，利用答案不超过6的特点，进行一定的减枝，使效率得以保证。
这篇关于（2019CSP模拟）DTOJ 4627. 灰烬的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
