洛谷P1120 小木棍 ［数据加强版］【搜索+毒瘤剪枝】

原题来源POJ - 1011 Sticks

时空限制 300ms-1000ms / 128MB

题目描述

乔治有一些同样长的小木棍，他把这些木棍随意砍成几段，直到每段的长都不超过50。 现在，他想把小木棍拼接成原来的样子，但是却忘记了自己开始时有多少根木棍和它们的长度。 给出每段小木棍的长度，编程帮他找出原始木棍的最小可能长度。

输入格式：

共二行。 第一行为一个单独的整数N表示砍过以后的小木棍的总数，其中N≤65 （管理员注：要把超过50的长度自觉过滤掉，坑了很多人了！） 第二行为N个用空个隔开的正整数，表示N根小木棍的长度。

输出格式：

一个数，表示要求的原始木棍的最小可能长度

说明

-#17 #20 #22 #27 四组数据时限500ms -#21 #24 #28 #29 #30五组数据时限1000ms 其他时限改为200ms

---

题目分析

练习搜索剪枝的绝世好(du)题(liu) 首先确定搜索思路在逐步加入剪枝

我们可以枚举原来每段木棍的长度len来搜索判断是否可行 先计算出木棍总长$sum$，显然$len$一定是$sum$的约数 确定了$len$的同时，我们也确定了原来木棍个数$cnt=sum/len$

for(len=mx;len<=sum;++len)//mx时切割后所有小木棍中最长的那个的长度 { if(sum%len) continue; cnt=sum/len; memset(vis,0,sizeof(vis)); if(dfs(1,0)) break; }

首先最简单最暴力的搜索，可得27pts

int dfs(int k,int m)//当前以拼完k-1个木棍，正在拼第k个，且第k个木棍当前长m { if(k==cnt+1) return 1;//拼完所有cnt个，方案合法 if(m==len) return dfs(k+1,0);//拼完了第k个，开始拼下一个 for(int i=1;i<=n;++i) { if(vis[i]||m+a[i]>len) continue; vis[i]=1;//尝试将第i个小木棍拼上去 if(dfs(k,m+a[i])) return 1; vis[i]=0; //回溯后记得重置 } return 0; }

现在开始考虑剪枝 1.一个最明显的剪枝就是一开始小木棍从大到小排序 这一点比较简单不解释了，排序后33pts

2.若当前木棍还没拼完，那么继续搜索拼接这个木棍的小木棍时 前面已枚举过的显然不用再考虑

剪枝后39pts

int dfs(int k,int m,int last)//last记录上一次枚举到的位置 { if(k==cnt+1) return 1; if(m==len) return dfs(k+1,0,1); for(int i=last;i<=n;++i)//从last开始枚举 { if(vis[i]||m+a[i]>len) continue; vis[i]=1; if(dfs(k,m+a[i],i+1)) return 1; vis[i]=0; } return 0; }

3.假如已尝试将某个长度为$a_i$的小木棍拼接到当前木棍不可行 那么相同长度的木棍不用再搜索

剪枝后54pts

int dfs(int k,int m,int last) { if(k==cnt+1) return 1; if(m==len) return dfs(k+1,0,1); int pre=0;//记录上一次用的长度 for(int i=last;i<=n;++i) { if(vis[i]||m+a[i]>len||a[i]==pre) continue;//计入a[i]==pre，相同则跳过的剪枝 vis[i]=1; if(dfs(k,m+a[i],i+1)) return 1; vis[i]=0; pre=a[i]; //到达这里说明ai不可行，用pre记录 } return 0; }

4.假设当前正在拼接的木棍长度为0 且第一次尝试将某个小木棍$a_i$拼接不可行后，直接回溯

因为若当前小木棍长度为0，说明剩余没拼的木棍都是等价的(都是0) 若把$a_i$放入当前木棍不可行，那么放入其他等价的木棍显然也不可行

剪枝后78pts

int dfs(int k,int m,int last) { if(k==cnt+1) return 1; if(m==len) return dfs(k+1,0,1); int pre=0; for(int i=last;i<=n;++i) { if(vis[i]||m+a[i]>len||a[i]==pre) continue; vis[i]=1; if(dfs(k,m+a[i],i+1)) return 1; vis[i]=0; pre=a[i]; if(m==0) return 0;//若第一次搜索就不成功，直接回溯 } return 0; }

5.若当前正在拼接的木棍长度+当前枚举的小木棍长度$a_i$==$len$ 且此次向下搜索判定为不合法，则可以直接回溯

因为如果继续枚举，用两个更小的木棍凑出$a_i$，显然与上述也是等价的

剪枝后100pts

int dfs(int k,int m,int last) { if(k==cnt+1) return 1; if(m==len) return dfs(k+1,0,1); int pre=0; for(int i=last;i<=n;++i) { if(vis[i]||m+a[i]>len||a[i]==pre) continue; vis[i]=1; if(dfs(k,m+a[i],i+1)) return 1; vis[i]=0; pre=a[i]; if(m==0||m+a[i]==len) return 0; } return 0; }

---

完整代码

#include<iostream> #include<cstdio> #include<cmath> #include<queue> #include<algorithm> #include<cstring> using namespace std; int read() { int f=1,x=0; char ss=getchar(); while(ss<'0'||ss>'9'){if(ss=='-')f=-1;ss=getchar();} while(ss>='0'&&ss<='9'){x=x*10+ss-'0';ss=getchar();} return x*f; } const int maxn=100; int n,a[maxn],ans; int vis[maxn],stick[maxn]; int sum,mx,cnt,len; bool cmp(int a,int b){return a>b;} int dfs(int k,int m,int last) { if(k==cnt+1) return 1; if(m==len) return dfs(k+1,0,1); int pre=0; for(int i=last;i<=n;++i) { if(vis[i]||m+a[i]>len||a[i]==pre) continue; vis[i]=1; if(dfs(k,m+a[i],i+1)) return 1; vis[i]=0; pre=a[i]; if(m==0||m+a[i]==len) return 0; } return 0; } int main() { n=read(); for(int i=1;i<=n;++i) { int x=read(); if(x>50) continue; a[++cnt]=x; mx=max(mx,a[cnt]); sum+=a[cnt]; } n=cnt; cnt=0; sort(a+1,a+1+n,cmp); for(len=mx;len<=sum;++len) { if(sum%len) continue; cnt=sum/len; memset(vis,0,sizeof(vis)); if(dfs(1,0,1)) break; } printf("%d",len); return 0; }