欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

hdu1455 拼木棍(经典dfs)

程序员文章站 2022-03-25 17:35:15
给定木棍序列,求解能将木棍拼成相同长度的数根长木棍的情况下长木棍长度的最小值。 /*hdu1455dfs */ #include using namespace std; typedef unsigned int ui; typedef long long ll; ty ......

给定木棍序列,求解能将木棍拼成相同长度的数根长木棍的情况下长木棍长度的最小值。

/*hdu1455dfs
*/
#include<bits/stdc++.h>
using namespace std;
typedef unsigned int ui;
typedef long long ll;
typedef unsigned long long ull;
#define pf printf
#define prime1 1e9+7
#define prime2 1e9+9
#define scand(x) scanf("%llf",&x)
#define f(i,a,b) for(int i=a;i<=b;i++)
#define scan(a) scanf("%d",&a)
#define dbg(args) cout<<#args<<":"<<args<<endl;
#define pb(i) push_back(i)
#define ppb(x) pop_back(x)
#define maxn 100

int a[maxn],used[maxn],n; 
int tot,ans,target;
int flag;
void dfs(int now,int finish,int pos)
{
    if(flag)return;
    if(finish==tot/target)
    {
        flag=1;
        return;
    }
//    if(num+a[n]>target)return;//最短的一根木棍和当前木棍无法拼成,则搜索失败 
    f(i,pos,n)
    {
        if(used[i])continue;
        if(a[i]+now>target)continue;
        used[i]=true;
        if(now+a[i]==target)
        {
            dfs(0,finish+1,1);
        }
        else 
        {
            dfs(now+a[i],finish,i+1);
        }
        if(flag)return;
        used[i]=false;
        if(!now)return;//数根已经可以拼成target长度,但是剩余木棍中较长的一根作为首选无法达成要求,说明第一根会被废弃 
        while(a[i]==a[i+1]&&i+1<=n)i++;//前面用相同长度的木棍,无法拼成,则后面用同样长度的也不能拼成 
    }
}
int main()
{
    std::ios::sync_with_stdio(false);
    
    while(scan(n)==1&&n)
    {
        flag=0;
        tot=0;
        ans=0;
        f(i,1,n)
        {
            scan(a[i]);
            tot+=a[i];
        }
        sort(a+1,a+n+1,greater<int>());//降序 ,总是现用最长的木棍最为第一根检查是否可以拼接 
        f(i,a[1],tot) //实际上最长不可能超过tot/2, 
        {
            if(tot%i==0)
            {
                memset(used,0,sizeof(used));
                target=i;
                dfs(0,0,1);
                if(flag)
                {
                    ans=target;
                    break;
                }
            }
        }
        if(!flag)pf("%d\n",tot);
        else pf("%d\n",ans);
    }
    
 }