[数据结构与算法]--木棒--

木棒

题目描述

核心思路

首先明确一下概念：木棒指原来为被砍断的，木棍指砍断后的。

我们可以从小到大枚举原始木棒的长度的长度length(也就是枚举答案)。假设有$cnt$根原始木棒，设所有小木棍的长度之和为$sum$，那么有$cnt\times length=sum$，也就是说必然有length是sum的约数。

对于枚举的每个原始木棒的长度length，我们可以依次搜索每根原始木棒由哪些小木棍组成。搜索所面对的状态包括：

• 已经拼好的原始木棒的个数$u$（其实也就是当前在模拟第$u$根原始木棒的拼凑）
• 正在拼凑的这根原始木棒中的那些小木棍的长度之和$cur$
• 这根原始木棒中的拼凑的起始小木棍的编号$start$

在每个状态下，我们从尚未使用的小木棍中选择一个，尝试放入当前的这根原始木棒中，然后递归到新的状态。递归边界就是成功拼好这$cnt$根原始木棒，或者因为无法继续拼接而宣告失败。

考虑剪枝优化：

这里的（3）和（4）剪枝特别难理解…

代码：

#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=70;
int w[N];   //存储小木棍的长度
bool st[N]; //标记某根小木棍是否已经被使用过了
//sum是所有小木棍的长度总和  length是枚举的原始木棒的长度
int n,sum,length;

//u表示当前枚举的是第u根原始木棒
//cur表示当前枚举的第u根原始木棒时,这个木棒里面的那些已经拼凑好的木棍长度之和是cur
//start表示枚举第u根原始木棒时 这个木棒中拼凑的起始木棍编号
bool dfs(int u,int cur,int start)
{
    //已经模拟完了u根原始木棒 发现它们的长度之和已经等于sum了 则是合法解
    if(u*length==sum)
        return true;
    //如果当前原始木棒中那些已经拼凑好的木棍长度之和已经是这根原始木棒的长度
    //那么我们就继续去模拟下一根原始木棒 讨论看看下一根原始木棒该怎么拼凑出来
    if(cur==length)
        return dfs(u+1,0,0);    //u+1表示下一个原始木棒
    //对于模拟的这跟原始木棒 它组内的木棍编号的从大到小的
    for(int i=start;i<n;i++)
    {
        //如果i这根小木棍已经被用过了 则跳过
        if(st[i])
            continue;
        //如果把i这根小木棍放进这个组内 使得长度之和大于这根原始木棒的长度 则不把i放进来 跳过
        if(cur+w[i]>length)
            continue;
        st[i]=true; //标记i这根小木棍已经被用过了
        //如果把i这根小木棍放进该组内 可以满足条件 则返回true
        if(dfs(u,cur+w[i],i+1))
            return true;
        //恢复现场
        st[i]=false;
        //cur==0表示拼凑第一根小木棍就失败了
        //cur+w[i]==length表示拼凑最后一根小木棍失败了
        if(cur==0||cur+w[i]==length)
            return false;
        int j=i;
        //如果把i这根小木棍放进这个模拟的原始木棒中不合法  那么就跳过所有木棍长度与i相等的木棍
        while(j<n&&w[j]==w[i])
            j++;
        //这里要记得让i=j-1 因为我们最后还要执行for中的i++
        //比如 5 5 5 6  结束while循环j指向6 执行i=j-1后 i指向最后一个5
        //最后再执行i++  那么i就指向6了
        i=j-1;
    }
    //枚举完了还没有成功,就返回失败
    return false;
}

int main()
{
    while(cin >>n,n)
    {
        memset(st,0,sizeof st); //清空上一次的状态
        sum=0;  //清空上一次的状态
        for(int i=0;i<n;i++)
        {
            scanf("%d",&w[i]);
            sum+=w[i];  //计算这些木棍的总和
        }
        sort(w,w+n);    //排序
        reverse(w,w+n); //将木棍从大到小排序
        //对于枚举原始的这些等长木棒  我们从小到大开始
        //这样当找到第一个满足条件的木棒的长度时  它一定是最小的原始木棒长度
        length=1;
        while(1)
        {
            //小木棍的总长度是sum 而这些小木棍组成了那些等长的原始木棒
            //因此那些原始木棒的长度之和也是sum 假设有cnt根原始木棒 而每根原始木棒的长度为length
            //那么一定有cnt*length=sum  因此sum一定可以除尽length
            //u=0其实就是枚举第一根原始木棒
            //cur=0表示枚举的第一根原始木棒中那些小木棍的长度之和为0
            //start=0表示枚举的第一根原始木棒中所,第一个小木棍的编号为0
            if(sum%length==0&&dfs(0,0,0))
            {
                printf("%d\n",length);
                break;  //找到第一个满足条件的原始木棒的长度  直接break
            }
            //尝试让原始木棒长度增大
            length++;
        }
    }
}