P1120小木棍结题报告

NoyException · 2018-12-08 16:04:19 · 题解

题目链接： [P1120] (https://www.luogu.org/problemnew/show/P1120) 本蒟蒻花了半天才肝出来这道题，见到AC时内牛满面……

题目解释

看到这个题目你可能会无从下手~~（其实无从下手的只是我自己而已）~~，但人家的数据范围也才不过65×50，用暴搜就行了。

至于题目中的“舍去长度超过50的小木棍”的意思是，你不用理那些超过50的数据，直接扔掉就行了。

那究竟该怎么暴搜呢？很明显BFS是顶不住了，那么我们就用深搜。我刚开始的思路,就是遍历所有的可能组合的长度，然后再对50根木棒进行全排序，排序过程中再进行剪枝，时间复杂度~~也不过就~~是O(n!*m)而已，65！*m的话……那肯定会爆炸啦！所以接下来我就来为大家介绍一下怎么剪枝。Here we go!

如何剪枝

（名词说明：原长：可能的原木棍长度，小木棍/木棍/大木棍：还未拼接的木棍，原木棍：长度为原长的已经拼好的木棍）

1：基础剪枝

I首先，我们需要对这些进来的数据排个序，大的在前小的在后。为什么呢？因为~~打怪的时候不都是先开大再A一下补刀的吗~~排好序的数组更方便优化2的操作，而且小的木棒灵活性更强，放在前面可以组合出非常多没用的结果，你想想看大木棒都被你扔一边去了，小木棍给用完了，到时候怎么拼成长度一样的木棍？

II其次我们很容易也可以知道，如果尝试将一小段木棒拼上去却没有成功的话，那么以后也就别再尝试其它的长度相同的木棒了，直接一个nxt数组转到下一个。而nxt数组也是只有在优化I后才可以建立的。

III经过一番哲学分析我们可以发现，拼好的木棍的长度肯定是所有砍成的小木棍长度之和的因数。也就是说，在遍历所有的原长时，应该判断木棍总长是否可以整除原长。

IV使用vis数组来存储是否使用过某木棍，而撤销使用时记得将vis改掉。

2：普通剪枝

V我们可以清楚得知道，所有的木棍都是要用来拼接的，不能说丢掉某一根看着不中意的木棍。所以呢，当你已经拼好了一根原木棍，开始尝试拼新的一根木棍时，请选择最大的那根还没用来拼接的木棍，反正迟早要用上。（至于为什么用最大的参见剪枝I）

VI在拼一根原木棍的时候注意，一定要从比上一根拼进此原木棍的木棍长度更小的木棍开始尝试拼接。你想想你曾经尝试过将一根大木棍拼进去发现拼不了，选了一个较小的，现在叫你选下一根，你却又选了那根大木棍……（警告：当你开始拼一根新的原木棒时请从头开始尝试拼接）

VII当你还剩最后一根原木棒没有拼接时直接返回成功。因为根据III你已经进行过整除判断了，剩余的小木棒的长度总和必定就是原长，而且不管怎么拼都没问题。

3：进阶剪枝

VIII如果发现在实现V之后最大的那根木棍无法与其他的木棍拼成原木棍，则直接返回上一级拆了上一根原木棍重新拼，因为如果不这么做的话最长的那根木棍是永远无法拼成原木棍的。

IX若你在拼一个原木棒时还剩i个单位的长度没拼上时，恰好有一根长度就是i的木棒，那么优先选这个（这个在前面的优化里说了，重点在后面），但如果这根木棒拼进去后发现剩余的木棒是不能组合成原木棒的，那么直接返回失败，因为你要换这根木棒也只能换成长度更小的几段，使剩余木棒的灵活性反而更低，就更不可能拼成原木棒。所以直接返回去重做上一根原木棒。

上代码

说了这么多，应该已经够了吧。至于那些大神剪枝我是不会的，反正够写出这道题就行了。那么就有请各位客官来看一下我的代码吧，献丑了~~（555本人蒟蒻【一脸害羞】555神犇勿喷【一脸害怕】）~~

#include <bits/stdc++.h>
using namespace std;

int line[65],len,nxt[65],end,sum;
bool vis[65];
bool cmp(const int a,const int b)
{
    return a>b;
}
bool perm(int pre,int fromp)
{
    int i;
    if(pre%len==0)
    {
        if(sum-pre==len) return true;//优化VII 
        for(i=2;i<=end && vis[i];i++) ;//优化V 
        vis[i]=true;
        if(perm(pre+line[i],2)) return true;
        vis[i]=false;//后面是else不运行，直接到后面的return false；这就是优化VIII 
    }
    else for(;fromp<=end;fromp++)//优化VI，直接从继承过来的fromp开始遍历 
    {
        if(!vis[fromp])//优化IV 
        {
            if(pre%len+line[fromp]<=len)
            {
                vis[fromp]=true;
                if(perm(pre+line[fromp],fromp)) return true;//fromp即为优化VI
                vis[fromp]=false;
                if(pre%len+line[fromp]==len) return false;//优化IX 
            }
            fromp=nxt[line[fromp]];//优化II 
        }
    }
    return false;
}

int main()
{
    int n,iA,in,maxi=0,cha=0,cun=0;
    scanf("%d\n",&n);
    for (iA=1;iA<=n;iA++)
    {
        scanf("%d",&in);
        if(in<=50)
        {
            maxi=max(maxi,in);
            sum+=in;
            line[iA-cha]=in;
        }
        else cha++;
    }
    sort(line+1,line+n-cha+1,cmp);//优化I 
    for(iA=1;iA<=n-cha;iA++)
        if(line[iA]!=cun)
        {
            nxt[cun]=iA-1;
            cun=line[iA];
        }
    end=n-cha;vis[1]=true;nxt[line[end]]=end;
    for(len=maxi;len<=sum/2;len++)
    {
        if(sum%len!=0) continue;//优化III 
        if(perm(line[1],2)) break;
    }
    if(len>sum/2) cout<<sum;
    else cout<<len;
    return 0;
}

咳咳码字码的好辛苦，神犇勿喷哇，蟹蟹！（~~如果您能点个赞的话……~~想什么呢咳咳）

P1120小木棍 结题报告