题解 P1120 【小木棍 ［数据加强版］】

· · 题解

小木棍（数据加强）【题解】

其实，这题的难度很迷（我先在POJ上做的）；

至于为什么呢？

有一道数据原版的难度是省选

而原题（本题）是强化的，难度却是提高+ （迷）

废话不多说，进入正题；

其实这道题就是一个搜索，并且用上了剪枝。

划重点

所谓剪枝，就是减小搜索树的规模。尽早排除搜索树中不必要的分支的一种手段。形象地看，就好像剪掉了搜索树的枝条。

考虑以下剪枝：

1.逆序搜索

把木棍儿的长度从大到小排序；

2.X+Y=Y+X(好理解吧）

1）相同的只搜一遍；

2）如果现在已经拼成的长度，在后面是不可能成功的。那么我们就认定这个分支是失败的。所以如果之后的分支再次遇见像这样的长度。我们就直接把他给返回就可以了。

3）如果刚开始拼接木棒的时候，第一根已经导致了拼接失败。那我们就可以判定当前的大分支是不可行的。至于为什么，是因为他在第一次已经不行啦（开车）。那么它在其他木棒中也是不可以的。

其实大概的剪枝思想也就只这些；

下面上代码；

深搜代码

bool dfs(int now,int cab,int last)
//now表示现在在拼的第now根原始木棒
//cab表示第now根木棒的当前长度
//上一根小木棒是last
{
    if(now>s) return 1;//所有的木棒拼完了
    if(cab==l) return dfs(now+1,0,1);//l是拼完的长度，now根拼好了
    int f=0;//剪枝2，2）
    for(int i=last;i<=cnt;i++)//剪枝1
    {
        if(!k[i] && cab+a[i]<=l && f!=a[i])
        {
            k[i]=1;
            if(dfs(now,cab+a[i],i+1)) return 1;
            f=a[i];
            k[i]=0;//回溯
            if(cab==0 || cab+a[i]==l) return 0;//cab+a[i]==l加不加应该没影响
        }
    }
    return 0;//搜索失败
}

主函数

int main()
{
    int n;
    while(cin>>n&&n)//输入
    {
        memset(a,0,sizeof(a));//初始化
        memset(k,0,sizeof(k));
        cnt=0,v=0,sum=0,l,s;
        for(int i=1;i<=n;i++)
        {
            int x;
            cin>>x;
            if(x>50) continue;//题意，防止毒瘤测试点
            a[++cnt]=x;
            v=max(v,x);
            sum+=x;
        }
        sort(a+1,a+cnt+1);
        reverse(a+1,a+cnt+1);//STL翻转数组
        for(l=v;l<=sum;l++)
        {
            if(sum%l) continue;
            s=sum/l;//原始木棒长l，共cnt根，故每根长sum/cnt；
            memset(k,0,sizeof(k));
            if(dfs(1,0,1)) break;
        }
        cout<<l<<endl;//输出答案
    }
    return 0;//完美结束
}

完整代码 （拿走不谢）

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

int cnt=0,v=0,sum=0,l,s;
int a[100],k[100];

bool dfs(int now,int cab,int last)
{
    if(now>s) return 1;
    if(cab==l) return dfs(now+1,0,1);
    int f=0;
    for(int i=last;i<=cnt;i++)
    {
        if(!k[i] && cab+a[i]<=l && f!=a[i])
        {
            k[i]=1;
            if(dfs(now,cab+a[i],i+1)) return 1;
            f=a[i];
            k[i]=0;
            if(cab==0 || cab+a[i]==l) return 0;
        }
    }
    return 0;
}

int main()
{
    int n;
    while(cin>>n&&n)
    {
        memset(a,0,sizeof(a));
        memset(k,0,sizeof(k));
        cnt=0,v=0,sum=0,l,s;
        for(int i=1;i<=n;i++)
        {
            int x;
            cin>>x;
            if(x>50) continue;
            a[++cnt]=x;
            v=max(v,x);
            sum+=x;
        }
        sort(a+1,a+cnt+1);
        reverse(a+1,a+cnt+1);
        for(l=v;l<=sum;l++)
        {
            if(sum%l) continue;
            s=sum/l;
            memset(k,0,sizeof(k));
            if(dfs(1,0,1)) break;
        }
        cout<<l<<endl;
    }
    return 0;
}

求审过，（据说，考试前发题解会np++）

第一篇紫题题解 （太不容易了）， 最后安利下我的博客