luoguP1120小木棍(POJ

题意：

乔治有一些同样长的小木棍，他把这些木棍随意砍成几段，直到每段的长都不超过50，个数不超过65。

现在，他想把小木棍拼接成原来的样子，但是却忘记了自己开始时有多少根木棍和它们的长度。

给出每段小木棍的长度，编程帮他找出原始木棍的最小可能长度。

思路：搜索+减枝。至于复杂度，很难计算，反正疯狂减枝就对了。

sum为总长度和，那么我们从小到大枚举sum的因子，验证是否成立。

#include<bits/stdc++.h>

using namespace std;

const int maxn=;

int vis[maxn],a[maxn],N,L;

bool dfs(int left,int now,int pos)

{

    if(left==&&now==) return ;//终止

    if(now==) { now=L; pos=; }

    for(int i=pos+;i<=N;i++){

        if(vis[i]||a[i]>now) continue; //不符合

        if(!vis[i-]&&a[i]==a[i-]) continue; //减枝1

        vis[i]=;

        if(dfs(left-,now-a[i],i)) return ;

        vis[i]=;

        if(a[i]==now||now==L) return ; //减枝2

    }

    return ;

}

int main()

{

    int sum,ans;

    while(~scanf("%d",&N)&&N){

        sum=;

        for(int i=;i<=N;i++) vis[i]=;

        for(int i=;i<=N;i++){

            scanf("%d",&a[i]);

            if(a[i]>) {

                i--; N--;

            }

            else sum+=a[i];

        }

        sort(a+,a+N+);

        for(int i=;i<=N/;i++) swap(a[i],a[N+-i]);

        ans=sum;

        for(L=a[N];L<=sum;L++){

            if(sum%L!=) continue;

            if(dfs(N,L,)){

                ans=L; break;

            }

        }

        printf("%d\n",ans);

    }

    return ;

}

巴特西

luoguP1120小木棍(POJ - 1011 )

最新文章

热门文章