题目描述
乔治拿来一组等长的木棒,将它们随机地砍断,使得每一节木棍的长度都不超过 50 个长度单位。
然后他又想把这些木棍恢复到为裁截前的状态,但忘记了初始时有多少木棒以及木棒的初始长度。
请你设计一个程序,帮助乔治计算木棒的可能最小长度。
每一节木棍的长度都用大于零的整数表示。
思路
定义全部小木棍的长度和为sum
1. 从小到大枚举完全体大木棒的长度l
2. dfs每个小木棍能否组成n个完全体大木棒。n = sum / l;
思路还是很简单,具体可以去看视频。我的困惑在于剪枝3,4的正确性,后来明白是证明的陈述漏掉了很多条件。比如下面这个模糊的陈述-“如果放在第一根木棒或者放最后一根木棒失败了,那么一定不合法”-很容易理解错误。下面梳理一下我的理解。
剪枝3,4
如果直接看代码就会发现,这两个剪枝发生在枚举第i个小木棍,且能成为当前大木棒u的组成部分,并且剩余的小木棍无法组成剩下需要的大木棒。
for (int i = start; i < n; i ++){ //枚举第i个小木棍
if (part + w[i] > length) continue;// 能成为当前大木棒u的组成部分
if(dfs(u, part + w[i], i + 1)) return true;
// 剩余的小木棍无法组成剩下需要的大木棒,第i个小木棍未使用
if (part == 0 || part + w[i] == length) return false; //剪枝3,4。如果部分i放在第一个或者最后一个失败,整个失败。
}
这样就可以看到上面的陈述省略了重要的条件,正确的陈述是:
剪枝3: 如果当前dfs的状态是枚举的大木棒长度为l,第u个大木棒已经拼了part长度并且part小于l,并且第i个小木棍可以成为第u个大木棒的第一个部分(即第i个小木棍长度小于等于当前枚举的大木棒长度l),并且没有使用过的小木棍无法组成第u个大木棒剩余的部分和剩下的n-u个木棒,之后的深搜没有合法方案(可以进行剪枝)。
之后的深搜是指从dfs的状态(大木棒长度为l,第u个大木棒已经拼了part长度并且part小于l,第i个小木棍未使用分)能到达的状态。因为dfs的搜索可以被看一颗树。树上的节点即是dfs的状态。
剪枝3证明:假设之后的深搜有合法方案。之后的深搜第i个小木棍不是第u个大木棒的最后一个部分,那么第i个小木棍是第k个大木棒的一个部分。交换同一根大木棒的小木棍顺序没有影响,所以第i个小木棍是第k个大木棒的第一个部分。交换第u个大木棒和第k个大木棒,方案合法,与条件矛盾。
剪枝4: 如果当前dfs的状态是枚举的大木棒长度为l,第u个大木棒已经拼了part长度并且part小于l,第i个小木棍可以成为第u个大木棒的最后一个部分(即第i个小木棍长度等于l-part),并且不包含第i个小木棍的没有使用过的小木棍无法组成剩下的n-u个木棒,之后的深搜没有合法方案(可以进行剪枝)。
这里的之后的深搜是指从dfs的状态(大木棒长度为l,第u个大木棒已经拼了part长度并且part小于l,第i个小木棍未使用)能到达的状态。
剪枝4证明:假设之后的深搜有合法方案。之后的深搜第i个小木棍不是第u个大木棒的最后一个部分,那么第i个小木棍是第k个大木棒的一个部分。因为之后的深搜中第u个大木棒被补完了,所以存在几个小木棍的长度和=l-part=第i个小木棍长度。交换第i个小木棍和这几个几个小木棍,得到一个合法方案。这与条件矛盾。
C++ 代码
//这里填你的代码^^
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 70;
int w[N], n, s, length;
bool st[N];
bool dfs(int u, int part, int start){
if (u * length == s) return true; //u是已经拼完的棒子数量
if (part == length) return dfs(u + 1, 0, 0);
for (int i = start; i < n; i ++){
if(st[i]) continue;
if (part + w[i] > length) continue;
st[i] = true;
if(dfs(u, part + w[i], i + 1)) return true;
st[i] = false;
if (part == 0 || part + w[i] == length) return false; //剪枝3,4。如果部分i放在第一个或者最后一个失败,整个失败。
int j = i;
while (j < n && w[i] == w[j]) j ++;
i = j - 1; //j 是第最小的一个w[j] != w[i]
}
return false;
}
int main(){
while(cin >> n, n){
s = 0;
memset(st,0,sizeof st); //memset 运行时间很,放到里面while loop会tle
for (int i = 0; i < n; i ++) {
scanf("%d", &w[i]);
s += w[i];
}
//剪枝1: 优先放长的部分,快速逼近length
sort(w, w + n);
reverse(w, w + n);
length = w[0];
while(true){
if (s % length == 0) {
if (dfs(0, 0, 0)) {
printf("%d\n", length);
break;
}
}
length ++;
}
}
return 0;
}