洛谷 P1120 小木棍［数据加强版］ 题解【搜索】

点击量：114

    超级无敌神级剪枝？

目录

题目描述

乔治有一些同样长的小木棍，他把这些木棍随意砍成几段，直到每段的长都不超过50。

 

现在，他想把小木棍拼接成原来的样子，但是却忘记了自己开始时有多少根木棍和它们的长度。

 

给出每段小木棍的长度，编程帮他找出原始木棍的最小可能长度。

 

输入输出格式

输入格式：

共二行。

 

第一行为一个单独的整数N表示砍过以后的小木棍的总数，其中$ N\le 65$

（管理员注：要把超过50的长度自觉过滤掉，坑了很多人了！）

 

第二行为$ N$个用空个隔开的正整数，表示$ N$根小木棍的长度。

 

输出格式：

一个数，表示要求的原始木棍的最小可能长度。

 

输入输出样例

输入样例#1：

9
5 2 1 5 2 1 5 2 1

输出样例#1：

6

说明

-#17 #20 #22 #27 四组数据时限500ms

 

-#21 #24 #28 #29 #30五组数据时限1000ms

 

其他时限改为200ms（请放心食用）

题解：

    题目描述特别简单，因此剪枝是需要想一想的。

    首先，如果要凑出长木棍，那么长木棍的长度一定能整除所有木棍的长度和。接着，枚举下界从最大一根木棍的长度开始，因为最大的不可能再拆了。并且因为要找最小解，所以从小到大枚举。

    接着，对搜索过程进行分析，因为我们先选大的凑，剩下的决策就会少一些，那么把木棍降序排序，遍历顺序从大到小。如果失败就从下一个长度不同的木棍处开始枚举，预处理出nxt数组，表示失败后跳到哪里。如果加上当前枚举的木棍刚好凑成一根，再从头枚举。剩下的木棍刚好凑成整根（注意不是一整根），如果此时失败了，就说明既然从最大的枚举都失败了，剩下的不可能包含大的，也不可能成功了。

    如果此时只剩下长度为要检验的长度，就直接返回，最后一步不用做了，一定正确。还要枚举从第几个开始合法，也就是第一个小于等于当前与目标的差的数。这个可以二分，虽然60的常数不起眼，但是它带了指数的复杂度，还是要剪掉。

    上面提到的每一个剪枝都会对程序效率产生几十倍的影响，因此一定要考虑周全。这个题是训练搜索的一道好题。

Code：

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
int l[66],n;
bool cmp(int x,int y)
{
    return x>y;
}
int used[66],sum=0;
int nxt[66];
void dfs(int x,int now,int t,int fin)
{
    if(now==x)
    {
        now=0;
        t=1;
        fin++;
    }
    if(fin==sum/x-1)//提前一步结束
    {
        printf("%d\n",x);
        exit(0);
    }

    int L=t,R=n,mid;//二分位置
    while(L<R)
    {
        mid=L+R>>1;
        if(now+l[mid]>x)
            L=mid+1;
        else
            R=mid;
    }
    t=L;
    for(int i=t;i<=n;)
        if(!used[i])
        {
            used[i]=1;
            now+=l[i];
            dfs(x,now,i,fin);
            now-=l[i];
            used[i]=0;
            if(now*2==x||now==0||now+l[i]==x)
                break;
            i=nxt[i];//跳的时候直接跳到下一个合法
        }
        else
            i++;//可能相同长的木棍只用了一部分，所以只往后找一个
}
int main()
{
    int mx=0;
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&l[i]);
        if(l[i]>50)//过滤
        {
            i--;
            n--;
            continue;
        }
        mx=mx>l[i]?mx:l[i];
        sum+=l[i];
    }

    std::sort(l+1,l+1+n,cmp);//倒序排序
    for(int i=n;i>=1;i--)
        if(l[i]!=l[i+1])
            nxt[i]=i+1;
        else
            nxt[i]=nxt[i+1];
    for(int i=mx;i<sum;i++)
        if(sum%i==0)
            dfs(i,0,1,0);
    printf("%d\n",sum);//可以少搜一个，答案一定是sum
    return 0;
}