注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

TsReaper的博客

一起来玩算法竞赛吧~

 
 
 
 
 

日志

 
 

[题解]小木棍  

2015-06-29 21:41:44|  分类: 题解 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
关键字:剪枝。

Link&Limit


        [洛谷1120]  [codevs3498]
        时间限制:1000ms  空间限制:131072kb

Description


        乔治有一些同样长的小木棍,他把这些木棍随意砍成几段,直到每段的长都不超过50。
        现在,他想把小木棍拼接成原来的样子,但是却忘记了自己开始时有多少根木棍和它们的长度。
        给出每段小木棍的长度,编程帮他找出原始木棍的最小可能长度。

Input Format


        第一行为一个单独的整数N表示看过以后的小木柜的总数,其中N≤60
        (管理员注:要把超过50的长度自觉过滤掉,坑了很多人了!)
        第二行为N个用空个隔开的正整数,表示N根小木棍的长度。

Output Format


        仅一行,表示要求的原始木棍的最小可能长度。

Sample Input #1


9
5 2 1 5 2 1 5 2 1

Sample Output #1


6

        搜索题。设所有木棍长度和为sum,首先枚举原木棍可能的长度ans(sum mod ans = 0),之后一一将小木棍尝试填入以凑出ans的长度。当然,我们需要一些剪枝:
        1、将小木棍按长度从大到小排序。因为先放长木棍可以更快地缩小待填长度,从而更快搜索出答案。
        2、由于每根木棍都必须填入,所以凑出新木棍的第一根小木棍必须是可用小木棍中最长的。这种在搜索树深度不大时进行的剪枝是非常强力的。
        3、如果存在一根木棍,只要填入它就能凑齐一个ans的长度,我们就要优先考虑这根木棍(用很多根小木棍凑齐同样长度一般不优,因为小木棍更加灵活,其它地方可能更有用)。
        4、枚举木棍时,如果接下来所有木棍都用上还凑不齐ans,此时的枚举一定是不合理的。
        本题的4个剪枝其实也是许多搜索题中的通用剪枝,练习时还应多多考虑。

#include <stdio.h>
#include <stdlib.h>
int n,m = 0,ans,tot,l[65],cnt[55],pre[65];
short ok = 0;
int comp(const void *a, const void *b)
{
    return *(int*)b - *(int*)a;
}
void dfs(int dep,int sum,int sta)
{
    int i;
    if(dep>tot) { ok = 1; return;}
    for(i=sta;i<=n;i++)
    {
        if(sum+pre[n]-pre[i-1]<ans) break;
        if(!cnt[l[i]] || sum+l[i]>ans) continue;
        cnt[l[i]]--;
        if(sum+l[i] == ans) dfs(dep+1,0,m+1);
        else
        {
            if(ans-sum-l[i]<=50 && cnt[ans-sum-l[i]])
            {
                cnt[ans-sum-l[i]]--;
                dfs(dep+1,0,m+1);
                cnt[ans-sum-l[i]]++;
            }
            else dfs(dep,sum+l[i],i+1);
        }
        cnt[l[i]]++;
        if(ok||!sum) return;
    }
}
int main()
{
    int i,sum = 0;
    scanf("%d",&n);
    for(i=1;i<=n;i++)
    {
        scanf("%d",&l[i]);
        if(l[i]>50) m++;
        else { sum += l[i]; cnt[l[i]]++;}
    }
    qsort(l+1,n,sizeof(int),comp);
    for(i=1;i<=n;i++) pre[i] = pre[i-1] + l[i];
    for(ans=l[m+1];ans<=sum;ans++)
    {
        if(sum%ans) continue;
        tot = sum/ans;
        dfs(1,0,m+1);
        if(ok) break;
    }
    printf("%d",ans);
    return 0;
}

  评论这张
 
阅读(7)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018