AcWing 167. 木棒（搜索）

深度搜索 + 剪枝

感悟：开始的时候自己能写一些出来，基本就写个主函数，能想到两个剪枝条件，啊，还得加倍努力啊！！！刚开始听视频讲解的时候觉得有几个剪枝条件有点鸡肋，好像没有什么用，最后在自己深度思考的时候想要弄明白到底有什么差别的时候（因为少了几个剪枝条件就会TTL）才发现很有用，原来是我的理解没到位，再看一次视频讲解发现说的真的好，证明的很到位。

原题链接

题目思路

• 思路：肯定有num * len = sum，则求先sum，枚举len，看是否符合 num
• 参数：dfs(int u, int cur, int start); //数个，当前长度，本次枚举开始下标
• 返回条件：1. u == num (最终完成) 2. cur == len (进一步搜索)

从常用剪枝技巧开始

• 优化搜索顺序： 将小截木棍按长度大到小排
• 枚举对象的优化： len可以从小截木棍最长的开始到sum，且为sum的约数
• dfs 中剪枝
  1. 如果当前小截木棍和前一小截木棍的长度是一样的，但是前一小截木棍没有被选上，那么这截木棍也一定不会被选上。(冗余剪枝)
  2. 在拼一根新木棒的第一截的时候，进入深度搜索失败，那么整个都不用再试了，肯定是前面拼的过程出了问题。（可行性剪枝）
  3. 在拼一根木棒的最后一截的时候当前小截木棍正好，但进入深度搜索后失败（即后面的拼不成了），那么整个也不用再试了，肯定是前面拼的过程出了问题。（可行性剪枝）

证明：2 反证法，若后面还有机会完整拼完，那么一定会用到这一截木棍（‘第一截’），矛盾。
证明：3 反证法，若此处不用当前小截木棍，而换成其他截木棍组成等长的，再补上。那么这截放到后面可以完整拼成的话，是矛盾的，因为这截与刚才 '组成截' 等价，而刚才是拼不成的。

ACcode

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;

const int N = 65;
int s[N], vis[N];
int n, num = 0, len = 0;

inline int cmp(int x, int y){
    return x > y;
}

bool dfs(int u, int cur, int start)
{
    if(u == num) return true;
    if(cur == len) return dfs(u+1, 0, 0);
    for(int i = start; i < n; i++)
    {
        if(!vis[i]) continue;
        
        if(cur + s[i] <= len)
        {
            vis[i] = 0;
            if(dfs(u, cur+s[i], i+1)) return true;
            vis[i] = 1;
            
            // 剪枝3 如果是第一个木棒失败，则一定失败
            if(!cur) return false;
            
            // 剪枝4 如果是最后一个木棒失败，则一定失败
            if(cur + s[i] == len) return false;
            
            // 剪枝2 跳过相同木棒
            int j = i;
            while(j < n && s[j] == s[i]) j++;
            i = j-1;
        }
    }
    return false;
}

int main()
{
    while(scanf("%d", &n) == 1 && n)
    {
        int sum = 0;
        for(int i = 0; i < n; i++)
        {
            scanf("%d", &s[i]);
            sum += s[i];
        }
        
        // 剪枝：优化搜索顺序
        sort(s,s+n,cmp);
        len = s[0];
        
        for( ; len != sum; len++)
            if(sum%len == 0) 
            {   //条件优化
                num = sum/len;
                memset(vis,1,sizeof(vis));
                if(dfs(0,0,0)) break;
            }
        
        printf("%d\n", len);
    }
    return 0;
}