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;
}
分类: 所有

XZYQvQ

炒鸡辣鸡的制杖蒟蒻一枚QvQ

发表评论

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

你是机器人吗? =。= *