Sticks UVA - 307

最新推荐文章于 2021-07-25 11:27:54 发布

沐妖

最新推荐文章于 2021-07-25 11:27:54 发布

阅读量335

点赞数

分类专栏： # 紫书刷题文章标签： IDA*

本文链接：https://blog.csdn.net/sgsyacm/article/details/86574484

版权

紫书刷题专栏收录该内容

54 篇文章

订阅专栏

题意：有等长小木棍，将木棍随意砍成几段，直到每段的长度都不超过50.现在将木棍拼接成原来的样子，但是不记得最开始有多少木棍和它们的分别长度。给出每根小木棍的长度，编程找出原始木棍的最小可能长度，例如若砍完后有四根·，长度分别为1,2,3,4，则原来可能是2根长度为5的木棍，也可能是1根长度为10的木棍。

思路：1.统计所有木棍总长度sum，则原来木棍数每根木棍长度maxd必须被sum整除，即sum % maxd == 0;

2. 将砍完后的木棍按照从大到小排序，长的的木棍，需要连接的木棍可能较少，选择的范围比较小，复杂度较低。因此枚举maxd时从ans[0]（注意此时已经排序完成）开始，到sum /2为止，因为(sum/2,sum)区间内不再有sum的倍数。

3.如果匹配过程中，上一根木棍未被使用，此时这一根木棍和上一根木棍长度相等则不用再验证直接进行下一根木棍

4.一旦有一根木棍从头匹配未被匹配成功，立刻返回0

#include <bits/stdc++.h>
#define INF 0x3f3f3f3f
using namespace std;
typedef long long ll;
const int maxn = 10000 + 10;
int n,k,maxd,ans[maxn],vis[maxn];
int dfs(int len,int s,int j)
{
    if(len == maxd)
    {
        s++;
        j = len = 0;
    }
    if(s == k) return 1;
    for(int i = j + 1;i < n;i++)
    {
        if(vis[i] || len + ans[i] > maxd || (i && ans[i] == ans[i - 1] && !vis[i - 1])) continue;
        vis[i] = 1;
        if(dfs(len + ans[i],s,i)) return 1;
        vis[i] = 0;
        if(len == 0) return 0;
    }
    return 0;
}
int main()
{
    while(scanf("%d",&n) && n)
    {
        int sum = 0;
        for(int i = 0;i < n;i++)
        {
            scanf("%d",&ans[i]);
            sum += ans[i];
        }
        sort(ans,ans + n,greater<int>());
        for(maxd = ans[0];maxd <= sum / 2;maxd++)
        {
            memset(vis,0,sizeof(vis));
            if(sum % maxd) continue;
            vis[0] = 1;
            k = sum / maxd;
            if(dfs(ans[0],0,0))
            {
                printf("%d\n",maxd);
                break;
            }
        }
        if(maxd > sum / 2)
        {
            printf("%d\n",sum);
        }
    }
    return 0;
}