题目描述

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

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

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

先写一个暴力……

暴力最好写了,然后再考虑剪枝

这是暴力:记录一下当前那根大木棍已经接了多长,已经接了多少根大木棍和一根大木棍应该有多长。

当然暴力也可以加一个简单的剪枝:记录一下总长度,如果当前枚举的一根大木棍的应有长度不能整除总长度那就不搜。

void dfs(int seq,int nowlen,int steps)
{

    if (nowlen==sum/seq && steps<seq-1)
    {
        dfs(seq,0,steps+1);
        return;
    }
    if (steps==seq-1 && nowlen==sum/seq)
    {
        cout<<sum/seq;
        exit(0);
    }
    
    for (int i=1;i<=len;i++) if (!used[i] && nowlen+a[i]<=sum/seq)
    {
        used[i]=true;
        dfs(seq,nowlen+a[i],steps);
        used[i]=false;
    }
}

int main()
{
    scanf("%d",&len);
    int cache,len2=len,c1=1;
    for (int i=1;i<=len2;i++) 
    {
        scanf("%d",&cache);
        if (cache>50) { len--; continue; }
        
        a[c1]=cache;
        
        sum+=a[c1];
        minlen=min(minlen,a[c1]);
        c1++;
    }

    for (int i=len;i>=1;i--) if (sum%i==0) 
    {
        memset(used,0,sizeof(used));
        dfs(i,0,0);
    }
    
}

然后剪枝:

1.我们按长度排序,如果当前正在拼一根新的木棍,而且最大的一根小木棍加上当前的长度(应该是0)都不能满足枚举到的当前大木棍长度那就剪掉。

2.还是上述操作,不过是剪掉:整整一根小木棍都比当前枚举到的大木棍的长度长的情况(那样显然无解)

3.还是排序之后,记录一下上次尝试了哪一根小木棍(也就是长度)如果这次枚举到的小木棍的长度和上次相等那么也剪掉。

4.如果搜的目标是拼最后一根大木棍了,而且最后还无解,回溯回来了,那这组直接放弃。

就这些?

对,一共就这么六个剪枝 (排序&暴力的剪枝&1234)

试试刚刚才意识到的高亮操作

#include<cstdio>
#include<cstring>
#include<iostream>
#include<string>
#include<cmath>
#include<algorithm>
#include<iterator>
#include<utility>
using namespace std;

int len,a[100]={0};
int sum=0,divide,seq;
bool used[100]={false};

void dfs(int nowlen,int steps,int pos)
{
    if (steps==seq) { printf("%d\n",divide); exit(0); }
    
    if (nowlen==0)
    {
        while (used[pos]) pos--;
        if (a[pos]>divide) return;
    }
    
    int pre=-1;
    for (register int i=pos;i>=1;i--) if (!used[i] && a[i]!=pre && a[i]+nowlen<=divide)
    {
        used[i]=true;
        pre=a[i];
        
        if (nowlen+a[i]==divide)
        {
            dfs(0,steps+1,len);
            used[i]=false;
            return;
        }
        else
        {
            dfs(nowlen+a[i],steps,i-1);
            if (nowlen==0) { used[i]=false; return; }
            used[i]=false;
        }
        
    }
}

int main()
{
    scanf("%d",&len);
    int cache,len2=len,c1=1;
    for (int i=1;i<=len2;i++) 
    {
        scanf("%d",&cache);
        if (cache>50) { len--; continue; }
        
        a[c1]=cache;
        sum+=a[c1];
        c1++;
    }
    sort(a+1,a+len+1);
    
    for (int i=a[len];i<=sum;i++) if (sum%i==0)
    {
        divide=i;//每段的长度
        seq=sum/i;//段数
        dfs(0,0,len);
    }
    
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注

This site uses Akismet to reduce spam. Learn how your comment data is processed.