童程OJ1508 小木棍 困难- 深搜/剪枝

记忆步骤：
1.全局变量应该有木棍数组a和标记数组vis
主函数：
1.最小木棍长度len，标记是否有答案变量f
2.输入，并记录木棍的最大值maxx和全部长度sum
3.从大到小排序
4.遍历len从maxx到sum，如果sum刚好是len的倍数，那么证明有复原方案，进行深搜
dfs函数：
1.dfs(已经使用的木棍数量tot，当前复原木棍长度l，从第now根木棍开始)
2.如果标记f为真，结束搜索
3.如果使用木棍数量tot等于总数n并且此时木棍长度为0，证明所有木棍已经复原完毕，有结果，则标记f更新为1，结束搜索
4.记录上一次使用的长度为last等于-1，用于排除重复的复原方案
5.循环从第几根木棍开始，i从now到n
6.如果第i根木棍没有标记过，并且，当前长度l 加上 第i根木棍长度a[i] 小于等于目标木棍长度len，证明这根木棍能用
7.为了排除重复情况，先判断 l + a[i]是否等于last，如果等于那么是重复情况，则跳过
8.没有触发排重则把last记录为l + a[i]
9.标记第i根木棍
10.如果l+a[i]刚好等于len，证明刚好匹配，继续重新深搜dfs(木棍使用数量tot+1，当前长度为0，从第1根重新搜索）
11.否则说明l + a[i]还是小于len的，还要继续拼接木棍，继续从第i +1根开始搜索，dfs(木棍使用数量tot +1，当前长度则为l+a[i]，从i+1根木棍开始搜索），这里的原因是因为我们从大到小排序了，所以继续拼接木棍，只能从下一根开始
12.回溯，清空第i根木棍标记
13.剪枝：如果l刚好为0，或者 l+a[i]刚好等于目标长度len，说明此时已经是最优情况了，继续搜索是没有更好的方案的，l + a[i]等于len很好解释，都匹配成功了没必要继续匹配；l = 0，拿样例的2+2+2来举例，就会发现l = 0是回溯到了最初的时候，而此时所有的5+1情况都匹配完了，很明显也是没有继续匹配的方案，所以也要结束，不然我们继续搜索下去，遇见的木棍都是已经标记过的，所以没有必要继续搜索了

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e3+10,inf = 0x3f3f3f3f;
int a[N],vis[N];
int len,n,f;
void dfs(int tot,int l,int now)
{
    if(f)return;
    if(tot == n && l == 0)
    {
        f = 1;return;
    }
    int last = -1;
    for(int i = now; i <= n; i++)
    {
        if(vis[i] == 0 && l + a[i] <= len)
        {
            if(l + a[i] == last)continue;
            last = l + a[i];
            vis[i] = 1;
            if(l + a[i] == len) dfs(tot + 1,0,1);
            else dfs(tot + 1, l + a[i], i + 1);
            vis[i] = 0;
            if(l == 0 || l + a[i] == len)break; //没有更好的结果 
        }
    }
}
int main()
{
    cin >> n;
    int maxx = 0,sum = 0;
    for(int i = 1; i <= n; i++)
    {
        cin >> a[i];
        maxx = max(a[i],maxx);
        sum += a[i];
    }
    sort(a + 1, a + 1 + n, greater<int>());
    for(len = maxx; len <= sum; len++)
        if(sum % len == 0)
        {
            f = 0;
            dfs(0,0,1);
            if(f)break;
        }
    cout << len;
    return 0;
}