hdu1455 拼木棍（经典dfs）

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

/*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);
    }
    
 } 

 

原文链接:https://www.cnblogs.com/randy-lo/p/12384564.html
如有疑问请与原作者联系

标签：

版权申明：本站文章部分自网络，如有侵权，请联系：west999com@outlook.com
特别注意：本站所有转载文章言论不代表本站观点，本站所提供的摄影照片，插画，设计作品，如需使用，请与原作者联系，版权归原作者所有