考察的是对于剪枝DFS的运用。
思路:如果以DFS直接暴力来做,我们可以看到,其实这是一个组合型递归的问题。
我们DFS的是对于木棒的个数,以及对于木棒的长度进行遍历,从而找到合适的答案。
以这个角度来说,我们其实是在小木棍里面进行组合大木棒而已,也就是说,拼接的顺序是无关紧要的。那么我们就可以进行排序操作,而且是从大到小。为什么呢?为什么不能是从小到大呢?由于我们在拼接木棒的过程中,可选择的木棍很多,如果说我们一开始就选择比较大的,那么这个时候DFS的遍历数据是不是就缩小了一些呢?也就排除了比较大的一类数据。
然后就是剪枝了。我们从以下几个角度考虑:
1.首先我们应该清楚,如果一个木棒开始进行拼接第一个小木棍的时候,这时满足不了拼接条件,那么所有的小木棒在拼接这个木棒的时候都会失败,也就是在遍历这种可能性的时候没有方案。可以用反证法来证明这种观点,大家可以看这位大佬的证明,很详细。AcWing 167. 木棒(详细证明,图解版) - AcWing
2.同理,在我们拼接最后一个小木棒的时候刚好够长度,这个时候也是不能采取方案的,由于这样做出方案之后,后面拼接的小木棒也可能出现这种情况,但这个时候小木棒不会够用,就算移动到其他的木棒身上去,对于后面的木棒来说都是没有方案的。这个也可以用反证法证明。
3.以上判断完毕之后,这些都是可行性的剪枝分析,最上面的那个也是常见的遍历顺序分析。如果我们在上面的判断中知道了哪些木棒不能取,但是遍历后面的时候也可能出现和当前木棒一致的木棒长度,那么我们就可以进行跳过操作,不去遍历他,节省时间。
详细细节已经放在了注释里面:
上代码;
#include<iostream>
#include<stdio.h>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<vector>
#include<algorithm>
#include<stack>
#include<queue>
#include<sstream>
#include<numeric>
#include<map>
#include<limits.h>
#include<set>
#define MAX 70
#define _for(i,a,b) for(int i=a;i<(b);i++)
#define ALL(x) x.begin(),x.end()
using namespace std;
using PII=pair<int, int>;
int n,V,m,res=INT_MAX;
int length, sum;
int arr[MAX];
bool st[MAX];
bool dfs(int u, int nowLen, int start) {
if (u * length == sum)//方案已经出来了,也就是说最终已经满足条件了
return true;
if (nowLen == length)return dfs(u + 1, 0, 0);//这个时候已经拼接完一个木棒了,所以不用多余耗费时间在已经完成的子任务上花去时间
for (int i = start; i < n; i++) {
if (st[i])//这个数已经用过了
continue;
if (nowLen + arr[i] <= length) {//还没有拼接完成
st[i] = 1;
if (dfs(u, arr[i] + nowLen, i + 1)) return true;//如果说按照这个方法拼下去有方案,说明这个方案是可行的
st[i] = 0;//进行回溯,判断下一个木棍是否满足
}
if (!nowLen || nowLen + arr[i] == length)return false;
int j = i + 1;
while (j < n && arr[i] == arr[j])j++;//遇见与现在相同的数的时候,就可以跳过了,因为在上面已经判断完了,这种数不可能继续遍历下去让其他木棒成立的
i = j - 1;
}
return false;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(NULL); cout.tie(NULL);
while (cin >> n, n) {
sum =0;
length=0;
memset(st,0,sizeof st);
_for(i, 0, n)
{
cin >> arr[i];
sum += arr[i];
length = max(length, arr[i]);
}
sort(arr, arr + n, greater<int>());
while (1) {
if (sum % length == 0 && dfs(0, 0, 0)) {
cout << length << endl;
break;
}
length++;
}
}
return 0;
}