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

作者: wjyyy 分类: 搜索,解题报告 发布时间: 2018-08-04 21:55

点击量:20

 

    超级无敌神级剪枝?

 

题目描述

乔治有一些同样长的小木棍,他把这些木棍随意砍成几段,直到每段的长都不超过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;
}

说点什么

avatar
  Subscribe  
提醒
/* */