问题描述

乔治有一些同样长的小木棍,他把这些木棍随意砍成几段,直到每段的长都不超过50。现在,他想把小木棍拼接成原来的样子,但是却忘记了自己开始时有多少根木棍和它们的长度。给出每段小木棍的长度,编程帮他找出原始木棍的最小可能长度。

输入

第一行为一个单独的整数N表示砍过以后的小木棍的总数,其中N≤64。
第二行为N个用空个隔开的正整数,表示N根小木棍的长度。

输出

仅一行,表示要求的原始木棍的最小可能长度。

思路

依然还是爆搜。

代码

#include <bits/stdc++.h>
#define INF 0x3f3f3f3f
#define MAXN 70
using namespace std;

int n, a[MAXN], ans=INF, sum, cnt;
bool vis[MAXN];

bool CMP(int x, int y) {return x>y;}

bool dfs(int num, int len, int last)
{
    if(num>=cnt) return true;
    if(len==ans) return dfs(num+1, 0, 1);
    int fail=0;
    for(int i=last; i<=n; i++)
    {
        if(vis[i] || len+a[i]>ans || fail==a[i]) continue;
        vis[i]=true;
        if(dfs(num, len+a[i], i+1)) return true;
        fail=a[i]; 
        vis[i]=false;
        if(len==0) return false;
    }
    return false; 
}

int main()
{
    scanf("%d", &n);
    for(int i=1; i<=n; i++)
    {
        scanf("%d", &a[i]);
        if(a[i]>50) n--, i--;
        else sum+=a[i], ans=min(ans, a[i]);
    }

    sort(a+1, a+n+1, CMP);
    for(; ans<=sum; ans++)
    {
        if(sum%ans!=0) continue;
        cnt=sum/ans;
        memset(vis, 0, sizeof(vis));
        if(dfs(1, 0, 1)) break;
    }
    printf("%d\n", ans);
}

发表评论

邮箱地址不会被公开。 必填项已用*标注