洛谷P1120 小木棍 ［数据加强版］搜索

玄学剪支，正好复习一下搜索

感觉搜索题的套路就是先把整体框架打出来，然后再一步一步优化剪枝

1.从maxv到sumv/2枚举长度（想一想，为什么）

2. 开一个桶，从大到小开始枚举

3. 在搜索中，枚举到长度为x的木棍，则下一步也从x开始枚举

4. 如果当前长度为0或target却无解则break掉，很玄学QAQ….

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

const int maxn = 4000;

int w[maxn];

int  sumv, minv, maxv;

void dfs(int nums,int cur,int target,int p)

{

    if(nums == 0)

    {

        printf("%d",target);

        exit( 0 );

    }

    if(cur == target)

    {

        dfs(nums-1,0,target,maxv);

        return;

    }

    for(int i = p;i >= minv;--i)

        if(w[i] && i + cur <= target)

        {

            w[i] -= 1;

            dfs(nums,cur + i, target, i);

            w[i] += 1;

            if (cur == 0 || cur + i == target )  break;

        }

    return;

}

int main()

{

   // freopen("input.txt","r",stdin);

    int n;

    scanf("%d",&n);

    minv = maxn, maxv = -1;

    for(int i=1;i <= n; ++i)

    {

        int tmp;

        scanf("%d",&tmp);

        if(tmp > 50) continue;

        w[tmp] += 1;

        sumv += tmp;

        minv = min(minv,tmp);

        maxv = max(maxv,tmp);

    }

    for(int i = maxv;i <= sumv/2; ++i)

    {

        if(sumv % i != 0)continue;

        dfs(sumv/i,0,i,maxv);

    }

    printf("%d",sumv);

    return 0;

}