1. 题目

2. 题解

就是个搜索题。。。
必须加很多剪枝。。。

剪枝剪去我们的疯狂
——膜你抄

我搞了这几个剪枝：
1. 答案必然在最短的长度到长度之和之间。见代码第 29 行。
2. 当前枚举的答案必然可以整除长度之和。见代码第 30 行。
3. 拼一根目标棍子时，枚举过小木棍不再枚举。见代码第 9 行。
4. 如果当前最长的那根木棍刚好可以完成当前正在拼的目标木棍，但是却无法完成任务，直接返回失败。见代码第 15 行。
5. 如果当前的正在拼的目标棍子还没有被拼凑过（即它的剩余长度等于目标长度），但是向下搜索返回的是失败，则直接返回失败。见代码第 15 行。
6. 如果用当前棍子去拼凑当前正在拼的目标棍子返回的是失败，则说明这种棍子去都是失败的，剪掉。见代码第 16 行。

这题数据有误，需要在读入时过滤掉。

代码：

#include <bits/stdc++.h>
using namespace std;
int n,l[70],sum,ans,tot;
bool book[70];
bool dfs(int a,int b,int c)
{
    if(c==tot)return 1;
    if(!a)if(dfs(ans,1,c+1))return 1;
    for(int i=b;i<=n;i++)
        if(!book[i]&&l[i]<=a)
        {
            book[i]=1;
            if(dfs(a-l[i],i+1,c))return 1;
            book[i]=0;
            if(a==l[i]||a==ans)break;
            while(l[i]==l[i+1])i++;
        }
    return 0;
}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&l[i]),sum+=l[i];
        if(l[i]>50)sum-=l[i],i--,n--;
    }
    sort(l+1,l+1+n,greater<int>());
    for(ans=l[1];ans<=sum;ans++)
        if(sum%ans==0)
        {
            tot=sum/ans;
            if(dfs(ans,1,0))break;
        }
    printf("%d\n",ans);
    return 0;
}

【题解】小木棍［数据加强版］搜索 LUOGU – 1120

于2017年5月11日2017年5月11日由XZYQvQ发布

1. 题目

2. 题解

XZYQvQ

0 条评论

发表回复取消回复

【题解】小木棍 ［数据加强版］ 搜索 LUOGU – 1120

于2017年5月11日2017年5月11日由XZYQvQ发布

1. 题目

2. 题解

XZYQvQ

0 条评论

发表回复 取消回复

【题解】小木棍［数据加强版］搜索 LUOGU – 1120

发表回复取消回复