这道题可以说是搜索剪枝例题中的经典,涉及到的剪枝操作令人汗颜
如果能够完完全全吃透这道题,对剪枝的体悟一定能更深
题目大意就不再叙述了 绝不是因为我懒
为了方便,先人为规定一下,未拼接的木棒叫做 ” 木棒 ” ,已拼接的叫 ” 木棍 ”
我们知道搜索的剪枝无非就是:
1.优化搜索顺序
2.排除等效冗余
3.可行性剪枝
4.最优性剪枝
5.记忆化
嗯?好像有点多?
(1) 我们首先可以想到把木棒排序一下,优化搜索顺序
(2) 然后试着排除等效冗余,很明显长度相等的木棒是等效的 这怕不是废话
但是等等!!
我们将剪枝 (1) 、 (2) 合起来,呼之欲出的是 —— 桶排序!!!
桶排序真是好啊,排了序又把等效的木棒放在一起,还方便初始化,啧啧
(3) 接着来看可行性剪枝,对于当前拼接的木棍,如果拼不出,那么其实全局也已经失败了
因为我们从大到小使用木棒,大的木棒在这时用不掉,以后也肯定用不掉(拼接木棍的等效性)
(4) 还有最优性剪枝,在这里我们直接从小到大枚举可能的木棍长度(意思是能被木棒总长整除)以确保当前可行答案为最优
(5) 记忆化不在家,我们不必找它
至于搜索的细节,在代码中会呈现出来
代码实现
//有注释版
//3 ms 就能过的代码~
#include<bits/stdc++.h>
using namespace std;
const int N=60;
//木棒长度不超过 50 ,所以用桶排序空间上也是优的
int read()
{
static int x;x=0;
char ch;ch=getchar();
while(ch<'0'||ch>'9') ch=getchar();
while(ch>='0'&&ch<='9')
{
x=(x<<1)+(x<<3)+ch-'0';
ch=getchar();
}
return x;
}
int n,sum,len,maxn;
int t[N];
void clear()
{
sum=0;len=0;maxn=0;
memset(t,0,sizeof(t));
}
bool dfs(int rest,int now,int po)
{
//rest 指还需要拼接出几根木棍
//now 指当前拼接出木棍的长度
//po 是指针指,指向向当前可取最长木棒的下标,也是长度
if(rest==0) return true;
//因为是从小到大枚举,所以一旦有解即为最优
if(now==len) return dfs(rest-1,0,maxn);
//剪枝 [3] : 当前木棍拼接完整,但拼接接下来的木棍失败,立即回溯
for(int i=po;i>=0;--i)
//要一直枚举到 0 ,不然边界无返回值
if(t[i]&&now+i<=len)
{
//由于是桶排序,当前长度的木棒不行时就直接跳到下一长度了
--t[i];
if(dfs(rest,now+i,i)) return true;
++t[i]; //还原
if(now==0||now+i==len) return false;
/*剪枝 [3] : 当前拼接的木棍尝试拼入第一根木棒就失败
或拼入一根木棒后,木棍恰好拼接完整,但接下来的拼接却失败
一句话,遇到拼接失败就立即回溯
*/
}
}
int main()
{
while(1)
{
n=read();
if(n==0) break;
clear();
for(int i=1,x;i<=n;i++)
{
x=read();
if(x>50) --i,--n;
//勿忘题目条件
else
{
++t[x]; sum+=x;
//剪枝 [1] 、 [2] : 桶排序有效地解决了相同长度的木棒具有等效性问题
maxn=max(x,maxn);
}
}
for(int i=maxn;i<=sum;i++)
{
//剪枝 [4] : 从小到大枚举(木棍最短为最长的木棒)
if(i*2>sum)
{
printf("%d\n",sum);
break;
//省去一些不必要的枚举
}
if(sum%i) continue;
len=i;
if(dfs(sum/i,0,maxn))
{
printf("%d\n",len);
break;
}
}
}
return 0;
}
//无注释版(精简版)
#include<bits/stdc++.h>
using namespace std;
const int N=60;
int read()
{
static int x;x=0;
char ch;ch=getchar();
while(ch<'0'||ch>'9') ch=getchar();
while(ch>='0'&&ch<='9') {x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}
return x;
}
int n,sum,len,maxn;
int t[N];
void clear() {sum=0;len=0;maxn=0;memset(t,0,sizeof(t));}
bool dfs(int rest,int now,int po)
{
if(rest==0) return true;
if(now==len) return dfs(rest-1,0,maxn);
for(int i=po;i>=0;--i)
if(t[i]&&now+i<=len)
{
--t[i];
if(dfs(rest,now+i,i)) return true;
++t[i];
if(now==0||now+i==len) return false;
}
}
int main()
{
while(1)
{
n=read();
if(n==0) break;
clear();
for(int i=1,x;i<=n;i++)
{
x=read();
if(x>50) --i,--n;
else ++t[x],sum+=x,maxn=max(x,maxn);
}
for(int i=maxn;i<=sum;i++)
{
if(i*2>sum) {printf("%d\n",sum); break;}
if(sum%i) continue;
len=i;
if(dfs(sum/i,0,maxn)) {printf("%d\n",len); break;}
}
}
return 0;
}
希望对你有所帮助
dfs(int u,int part,int start)中start表示的是第u组的枚举位置,但是在一开始枚举的时候木棒中是没有木棍的,那么为什么start一开始为0呢?
用桶来避开同样的数据,真的是太牛X的思路,学习
超时了兄弟