167. 木棒

乔治拿来一组等长的木棒，将它们随机地砍断，使得每一节木棍的长度都不超过 50 个长度单位。

然后他又想把这些木棍恢复到为裁截前的状态，但忘记了初始时有多少木棒以及木棒的初始长度。

请你设计一个程序，帮助乔治计算木棒的可能最小长度。

每一节木棍的长度都用大于零的整数表示。

输入格式

输入包含多组数据，每组数据包括两行。

第一行是一个不超过 64 的整数，表示砍断之后共有多少节木棍。

第二行是截断以后，所得到的各节木棍的长度。

在最后一组数据之后，是一个零。

输出格式

为每组数据，分别输出原始木棒的可能最小长度，每组数据占一行。

数据范围

数据保证每一节木棍的长度均不大于 50。

输入样例：

9
5 2 1 5 2 1 5 2 1
4
1 2 3 4
0

输出样例：

6
5

1、整体分析
这道题的数据范围非常小，在这种情况下，大概率就是一道指数级别的算法，即我们的暴力枚举DFS。

这道题中让我们求的是最小长度，所以我们从小开始枚举木棒的长度，利用DFS去暴力枚举看看有没有可能枚举出一种合法的方案。如果可以的话，说明这就是最小长度，如果不可以的话，我们就继续枚举长度。

但我们的长度枚举的时候，只需要枚举所有木棍总和的约数即可。因为只有我们的木棒长度能够整除所有木棍总和的时候，才有可能是答案。

2、剪枝优化
剪枝优化总共分为下面几个方面：
优化搜索顺序，排除等效冗余，可行性剪枝，最优性剪枝，记忆化搜索。

（1）优化搜索顺序
对于一个木棍而言，它要么就是自己再去创造一个新的木棒，要么就接在已有的木棒的后面。每一种选择的背后都是一棵搜索树。选择越多，说明树的节点越多，时间越长。

因此，我们需要减少选择的个数，从而减少搜索树中的子树。所以，我们可以将木棍从大到小排序，从大开始枚举。这样对于我们的一个木棒长度而言，我们的木棍越长，那么留给后续木棍的选择空间就越小。从而减少了后续木棍的选择，进而减少了节点数目。

（2）排除等效冗余
对于一个木棒而言，组成该木棒的木棍之间的顺序是没有要求的，因为这些内部木棍之间的顺序变化并不会一引起木棒长度的变化。

也就是说，我们的DFS中要做的是组合型枚举，而不是排列型枚举。

（3）可行性剪枝
这里先给出结论，在某个新的木棒中，在“尝试接入的第一个木棍”的递归分支就返回失败的话，那么就直接判断失败即可，不需要再去更换当前的第一根木棍继续枚举。

为什么呢？

我们的第四组新的木棒是我们的目标，我们当前接入了该木棒内的第一根小木棍A，那么为了成功凑出正确长度的木棒。在后续的DFS中，我们就会去利用剩余的小木棍去枚举所有包含木棍A的可能方案。

如果当前分枝返回了失败，意思就是所有利用剩余的小木棍并且包含小木棍A的可能方案都无法凑出一个正确的长度。

由于我们必须用完所有的小木棍，所以我们后续的方案中肯定有一个包含A的方案，但是我们已经知道是不可能了，所以就不用再去枚举后面的方案了。

（4）最优性剪枝
如果当前的木棒在接入最后一根木棒A后，这根木棒的长度恰好满足了条件，但是在拼接剩余木棒的时候失败了。那么回溯后，我们就会更换当前的最后一个木棒A。由于我们木棍的长度是从大到小的，所以用来代替A的必定是更短的多根木棍，假设是B和C。

那么A和B + C是等价的。

也就是说，我们用A的地方，都能用B和C代替。但是，我们用B和C的地方不一定能用A代替，因为我们的A是没法拆分的。也就是说B+C的组合能拼出更多的可能。

那么在结尾是A的时候，我们利用B和C加剩余木棍都没能拼好，那么现在用A和剩余木棍也一定不会拼好。

#include
#include
#include
using namespace std;
const int N=70;
int a[N];
bool st[N];
int sum,length,n;//sum表示所有小木棍的总长度 length表示木棒的长度 
int cmp(int x,int y)
{return x>y;
}
//u表示当前是第几组 s表示当前组的木棍长度 start表示i从start开始遍历
bool dfs(int u,int s,int start)
{//表表找到了 返回tureif(u*length==sum) return true;if(s==length) return dfs(u+1,0,0);//相等则进行下一组 true要一直持续不断的返回,false同理//组合方式枚举 剪枝3-1for(int i=start;ilength) continue;st[i]=true;if(dfs(u,s+a[i],i+1)) return true;//因为前i个棍子都在第u组枚举了,所以直接从第i+1根棍子开始枚举st[i]=false;//为什么s=0则是第一根呢 如果s=0说明 一直回溯回溯回溯 然后回溯到最初值 回溯到第一跟失败了s=0if(s==0) return false;//剪枝3-3 如果第一根失败了则一定失败了//如果刚好相等 说明最后一根失败了 最后一根+s大于length回溯 若此时+a[i]相等说明是最后一根失败 if(s+a[i]==length) return false;//剪枝3-4 如果最后一个失败了则一定失败了while(a[i]==a[i+1]) i++;//剪枝3-2如果i失败了,那么长度跟i一样的棍子也一定失败}return false;}
int main()
{while(cin>>n){if(n==0) break;sum=0;memset(st,0,sizeof st);for(int i=0;i>a[i];sum+=a[i];}//优化搜索顺序 从大到小遍历 减少分支sort(a,a+n,cmp);length=a[0];while(1){//必须是刚好取整 否则不满足题意if(sum%length==0&&dfs(0,0,0)){cout<

100
2

68

#include 
#include 
#include 
#include using namespace std;const int N = 25, INF = 1e9;int n, m;
int minv[N], mins[N];
int R[N], H[N];
int ans = INF;void dfs(int u, int v, int s)
{if (v + minv[u] > n) return;if (s + mins[u] >= ans) return;if (s + 2 * (n - v) / R[u + 1] >= ans) return;if (!u){if (v == n) ans = s;return;}for (int r = min(R[u + 1] - 1, (int)sqrt(n - v)); r >= u; r -- )for (int h = min(H[u + 1] - 1, (n - v) / r / r); h >= u; h -- ){int t = 0;if (u == m) t = r * r;R[u] = r, H[u] = h;dfs(u - 1, v + r * r * h, s + 2 * r * h + t);}
}int main()
{cin >> n >> m;for (int i = 1; i <= m; i ++ ){minv[i] = minv[i - 1] + i * i * i;mins[i] = mins[i - 1] + 2 * i * i;}R[m + 1] = H[m + 1] = INF;dfs(m, 0, 0);if (ans == INF) ans = 0;cout << ans << endl;return 0;
}

5
7
12
15
77
0

1 2 4 5
1 2 4 6 7
1 2 4 8 12
1 2 4 5 10 15
1 2 4 8 9 17 34 68 77

#include
#include
using namespace std;
const int N=110;
int path[N];
int n;
bool dfs(int u,int length)
{if(u==length){if(path[u-1]==n) return true;return false;}bool st[N]={0};//标记两个数之和 出现过 即不在访问 排除等效冗余for(int i=u-1;i>=0;i--) //从大到小枚举 优化搜索顺序 path[]一定是单调递增的若是求该数 故从该数的上一个数开始枚举 求和{for(int j=i;j>=0;j--){int s=path[i]+path[j];//path[]一定是递增的 若是st[]标记过 说明存在过两个数加和相等 则不要 并且这个数一定小于n//若已经到了n-1层了就不会再走这里了if(st[s]||sn) continue;path[u]=s;//往下层走if(dfs(u+1,length)) return true;}}return false;
}
int main()
{while(cin>>n){if(n==0) break;path[0]=1;//最初一定是1 第二个数其实肯定也是2 1+1=2int length=1;while(!dfs(1,length))length++;//从第二个数开始for(int i=0;i

20 5
7
5
4
18
1

19

#include
#include
using namespace std;
const int N=1<<25; // k最大是25， 因此最多可能有2^25种方案
typedef long long ll;
int weight[N];  // weight存储能凑出来的所有的重量
int g[50]; //存储所有物品的重量
int w,n,k;
int ans,cnt=0;// 用ans来记录一个全局最大值
int cmp(int x,int y)
{return x>y;
}
void dfs1(int u,int s)
{// 如果我们当前已经枚举完第k个数（下标从0开始的）了 就把当前的s 加到weight中去if(u==k){weight[cnt++]=s;return ;}// 枚举当前不选这个物品dfs1(u+1,s);// 选这个物品, 做一个可行性剪枝if((ll)g[u]+s<=w) dfs1(u+1,s+g[u]);//计算和的时候转成long long防止溢出
}
void dfs2(int u,int s)
{if(u==n)// 如果已经找完了n个节点， 那么需要二分一下{int l=0,r=cnt-1;while(l>1;if(weight[mid]<=w-s) l=mid;else r=mid-1;}ans=max(ans,s+weight[l]);return ;}// 不选择当前这个物品dfs2(u+1,s);// 选择当前这个物品if((ll)g[u]+s<=w) dfs2(u+1,s+g[u]);
}
int main()
{cin>>w>>n;for(int i=0;i>g[i];// 优化搜索顺序（从大到小）sort(g,g+n,cmp);k=n>>1;dfs1(0,0);int t=1;// 做完之后， 把weight数组从小到大排序sort(weight,weight+cnt);// 判重for(int i=1;i

多组输入
每组数据第一行输入k M(k<=6,1<=M<=1e8)，表示有多少类物品
接下来k行，每行以Ai(1<=Ai<=100)开头，表示这类物品有多少个，接下来Ai个数，第j个为Vj(1<=Vj<=1e8),表示小L对这类物品的第j个的喜欢值是多少。

每组输出一行，表示方案数

#include
#include
#include
#include
using namespace std;
typedef long long ll;
const int N=110;
int v[N][N];
int a[N];
int k,w;
ll ans=0;
void dfs(int u,int s)
{if(u>k+1) return ;if(s>w){ll num=1;for(int i=u;i<=k;i++){num*=(a[i]+1);//若已经遍历出来大于w 直接乘后面的组合数就行 +1是因为可以不选}ans+=num;return ;}for(int i=1;i<=a[u];i++){dfs(u+1,s+v[u][i]);//选}dfs(u+1,s);//不选
}
int main()
{while(cin>>k>>w){ans=0;for(int i=1;i<=k;i++){cin>>a[i];for(int j=1;j<=a[i];j++){cin>>v[i][j];}}dfs(1,0);cout<

#include 
using namespace std;
typedef long long ll;
const int N=105;
const int M=1e6+5;
int k,m;
int a[10];
int v[10][N];
ll ans=0;
ll w[M];
ll tot=0;
void dfs1(int u,int val)
{if(u>k/2){w[tot++]=val;return;}for(int i=1;i<=a[u];i++){dfs1(u+1,val+v[u][i]);}dfs1(u+1,val);
}//预处理k/2的void dfs2(int u,int val)
{if(u>k){ans+=tot-(upper_bound(w,w+tot,m-val)-w);return;}for(int i=1;i<=a[u];i++){dfs2(u+1,val+v[u][i]);}dfs2(u+1,val);
}int main()
{while(cin>>k>>m){ans=0;tot=0;for(int i=1;i<=k;i++){cin>>a[i];for(int j=1;j<=a[i];j++){scanf("%d",&v[i][j]);}sort(v[i]+1,v[i]+1+a[i]);}dfs1(1,0);//层数 价值sort(w,w+tot);dfs2(k/2+1,0);cout<

3
6
1 3 4 6 2 5
5
5 4 3 2 1
10
6 8 5 3 4 7 2 9 1 10

2
3
5 or more

#include 
#include using namespace std;const int N = 15;int n;
int q[N];  // 书的编号
int w[5][N];  // 恢复现场使用// 估价函数
int f() {int cnt = 0;for (int i = 0; i + 1 < n; i++)if (q[i + 1] != q[i] + 1)cnt++;return (cnt + 2) / 3;
}// 检查序列是否已经有序
bool check() {for (int i = 0; i + 1 < n; i++)if (q[i + 1] != q[i] + 1)return false;return true;
}// k: 当前迭代深度; depth: 迭代加深最大深度
bool dfs(int depth, int max_depth) {if (depth + f() > max_depth) return false;if (check()) return true;for (int len = 1; len <= n; len++)  // 先遍历长度for (int l = 0; l + len - 1 < n; l++) {  // 再遍历左端点int r = l + len - 1;for (int k = r + 1; k < n; k++) {memcpy(w[depth], q, sizeof q);int x, y;// 将上图中绿色部分移动到红色部分for (x = r + 1, y = l; x <= k; x++, y++) q[y] = w[depth][x];// 将上图中红色部分移动到绿色部分for (x = l; x <= r; x++, y++) q[y] = w[depth][x];if (dfs(depth + 1, max_depth)) return true;memcpy(q, w[depth], sizeof q);}}return false;
}int main() {int t;cin >> t;while (t--) {cin >> n;for (int i = 0; i < n; i++) cin >> q[i];int depth = 0;while (depth < 5 && !dfs(0, depth)) depth++;if (depth >= 5) cout<<"5 or more"<

1 1 1 1 3 2 3 2 3 1 3 2 2 3 1 2 2 2 3 1 2 1 3 3
1 1 1 1 1 1 1 1 2 2 2 2 2 2 2 2 3 3 3 3 3 3 3 3
0

AC
2
DDHH
2

#include
using namespace std;
const int op[8][7]={//记录每一种操作对应的数字坐标{0,2,6,11,15,20,22},{1,3,8,12,17,21,23},{10,9,8,7,6,5,4},{19,18,17,16,15,14,13},{23,21,17,12,8,3,1},{22,20,15,11,6,2,0},{13,14,15,16,17,18,19},{4,5,6,7,8,9,10}
};
const int opposite[8]={5,4,7,6,1,0,3,2};//记录每一种操作的逆操作
const int center[8]={6,7,8,11,12,15,16,17};//记录目标的八个格子的数字坐标
int path[100],q[25];
int f()//估价函数
{int sum[4]={0};for(int i=0;i<8;i++)//记录目标八个格子中每个数字出现的次数sum[q[center[i]]]++;int MAX=0;for(int i=1;i<=3;i++)//找出出现次数最多的数的个数MAX=max(MAX,sum[i]);return 8-MAX;
}
void operate(int x)//执行当前操作
{int t=q[op[x][0]];for(int i=0;i<6;i++)//每个格子向后移动一个q[op[x][i]]=q[op[x][i+1]];q[op[x][6]]=t;
}
bool dfs(int depth,int max_depth,int last)
{if(depth+f()>max_depth)//当前状态加上预期步数大于最大可扩展深度return false;//立即返回falseif(!f())return true;for(int i=0;i<8;i++)if(opposite[i]!=last){//当前操作不是上一步操作的逆操作operate(i);//执行当前操作path[depth]=i;//记录路径if(dfs(depth+1,max_depth,i))//如果搜索到答案return true;//返回trueoperate(opposite[i]);//回溯}return false;//无解
}
int main()
{while(cin>>q[0]&&q[0]){for(int i=1;i<24;i++)scanf("%d",&q[i]);int depth=0;//跌代加深while(!dfs(0,depth,-1))//当前深度无法得到答案depth++;//扩展深度if(!depth)printf("No moves needed");else{for(int i=0;i

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！