POJ1011Sticks

发表于: 2013年02月03 00:00

题意大概是:有一些棍子,现在需要把他们拼接恢复成若干根长度相同的棍子. 求这些棍子的最小长度

这题和poj2362类似.减枝的部分见代码

:::c++
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
#define MAX 70
int ss[MAX],n,avg;
bool vis[MAX];
int cmp(int a,int b)
{
    return a>b;
}
bool dfs(int sum,int num,int k)
{
    if(num==n)
        return true;
    int last=-1;
    for(int i=k;i<n;i++)
    {
        if(vis[i]) continue;
        if(ss[i]==last) continue;//先前出现过的,不在搜索
        vis[i]=true;
        if(ss[i]+sum<avg)//如果小于最短长度,继续
        {
            if(dfs(ss[i]+sum,num+1,i))
                return true;
            else 
                last=ss[i];
        }
        else if(ss[i]+sum==avg)
        {
            if(dfs(0,num+1,0))
                return true;
            else
                last=ss[i];
        }
        vis[i]=false;//回朔,恢复先前的状态
        if(sum==0) break;
    }
    return false;
}
int main()
{
    int sum;
    while(scanf("%d",&n)&&n)
    {
        avg=0;
        sum=0;
        for(int i=0;i<n;i++)
        {
            scanf("%d",&ss[i]);
            sum+=ss[i];
        }
        sort(ss,ss+n,cmp);//从大到小排序,dfs时可以减枝
        int flag=1;
        for(avg=ss[0];avg<sum;avg++)//从小到大,枚举最短长度
        {
            if(!(sum%avg))//不能整除的直接跳过
            {
                memset(vis,false,sizeof(vis));
                if(dfs(0,0,0))
                {
                    printf("%d\n",avg);
                    flag=0;
                    break;
                }
            }
        }//for
        if(flag)
            printf("%d\n",sum);
    }//while
}
© 2018 - fluyy - 粤ICP备17114935号