蓝桥集训之木棒

蓝桥集训之木棒

• 核心思想：dfs + 剪枝

  • 暴搜 : 将所有木棒从大到小排序 搜索

    • 从小往大 遍历所有可能长度

  • 剪枝 : 失败后 注意一定是当前木棍失败后**(无解)**

    • 1.跳过所有与当前木棍长度相同的木棍
    • 2.第1个未被使用的木棍如果作为新长木棍的第一根无解 则回溯
    • 3.若当前木棍加在当前长木棍上满足长度 则回溯

    

•   #include
    #include
    #include
    
    using namespace std;
    const int N = 70;
    
    int n;
    bool st[N];
    int w[N];
    int sum,len;
    
    bool dfs(int u,int cur,int start)  //u为长木棍数量 cur为当前长木棍长度 start为当前木棍编号
    {
        if(u * len == sum) return true;  //全部拼出来
        if(cur == len) return dfs(u+1,0,0);  //当前这根拼完
    
        for(int i=start;i<n;i++)
        {
            if(st[i]) continue;  //被搜过
            if(cur+w[i] <= len)
            {
                st[i] = true;
                if(dfs(u,cur+w[i],i+1)) return true;
                st[i] = false;  //恢复现场
            }
    		//失败后
            if(!cur || cur + w[i] == len) return false;  //2 3剪枝
            int j = i+1;
            while(j<n && w[i] == w[j]) j++;  //1剪枝
            i = j-1;
        }
        return false;
    }
    int main()
    {
        while(cin>>n , n)
        {
            sum = len = 0;
            for(int i=0;i<n;i++)
            {
                cin>>w[i];
                sum += w[i];
                len = max(len,w[i]);  //取最长木棍
            }
    
            sort(w,w+n,greater<int>());
            memset(st,0,sizeof st);
    
            while(true)
            {
                if(sum % len == 0 && dfs(0,0,0))  //len从最长小木棍开始++
                {
                    cout<<len<<endl;
                    break;
                }
                len++;
            }
        }
        return 0;
    }
  1
  2
  3
  4
  5
  6
  7
  8
  9
  10
  11
  12
  13
  14
  15
  16
  17
  18
  19
  20
  21
  22
  23
  24
  25
  26
  27
  28
  29
  30
  31
  32
  33
  34
  35
  36
  37
  38
  39
  40
  41
  42
  43
  44
  45
  46
  47
  48
  49
  50
  51
  52
  53
  54
  55
  56
  57
  58
  59
  60
  61