题解 UVA307 【小木棍 Sticks】

注: 下文中初始木棍指答案所求木棍,小木棍指输入的木棍.

第一眼看到这个题,感觉就是个无脑搜索,然后……~~暴0快乐~~

具体搜索的思路就是枚举初始木棍的长度,然后直接搜索每根木棍是由哪些小木棍拼成的.

但是,这样搜索肯定会TLE,所以我们要稍稍进行一点剪枝:

初始木棍长度大于等于最长的小木棍的长度,小于等于所有小木棍的总长,我们可以依次缩小枚举答案的范围.
小木棍总长肯定是初始木棍长度的倍数,所以我们只在$sum / len = 0$时进行搜索.
如果初始木棍长度到达$sum/2$时依然无解,这就说明即使把所有小木棍拼成两根时依然误解,于是我们可以直接让这些小木棍拼成一根,即如果当长度从$1$到$sum/2$枚举完一遍后依然无解,那么无须枚举$sum/2+1$到$sum$的部分,直接输出$sum$(即让所有木棍拼成一根)即可.
较短的木棍应用起来比长的木棍运用灵活,即如果一根长木棍可以用几根短木棍拼成,那么如果这根长木棍长度合适,那么优先选长木棍表达这一长度一定不会劣于用那些小木棍拼成这个长度,所以我们可以将木棍从大到小排序后优先选取长的木棍进行拼接.
如果我们将木棍从大到小排序以后,当我们在尝试拼第$k$根初始木棍时,可以记录上一次选取木棍$last$,然后在$last + 1$到$n$的范围内去枚举下一根木棍放什么(因为木棍$1$到$last$放或不放在之前肯定已经搜索过了).
对于相同长度的木棍$a_i$,$a_j$,如果我们在第$k$根放$a_i$是发现无法拼成想要的长度,那么放$a_j$肯定也拼不出来你想要的长度,直接while循环弹掉即可(ps:暴力弹数在时间复杂度上没有问题,如果你想追求极致的速度体验,那么你可以通过二分来求下一个枚举的木棍或把相同长度的木棍压在一起并记录总量).
如果当前要拼第$k$根原始木棍,而你现在还没有开始拼,那么我们本轮搜索可以强制选择当前可以选择的最长的木棍,因为当前我们还一根木棍都没有选,而这根最长的木棍迟早都要选,那么我们不如在这一轮直接选择它,这也体现了我们从大到小枚举的原则.如果我们选择这根木棍后最终无发拼出我们想要的等长的若干根木棍,那么如果选择先拼其他木棍也无法改变这个结果–也就是说,肯定是之前确定的方案出现了问题(不合法,最终无法构造成功),那么我们可以直接回溯到上一层继续搜索.
如果加入当前枚举到的木棍以后直接可以拼出我们想要的长度$len$,那么根据优化$4$中所说的原因,直接加入它肯定是最优的,于是我们就不用考虑去拼其它的木棍了,因为如果选择最优方案都无法拼出答案,那么选择其它的方案就更不可能了.

code:

#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<algorithm>
#define ll long long
#define INF 0x7fffffff
#define re register

using namespace std;

int read()
{
    register int x = 0,f = 1;register char ch;
    ch = getchar();
    while(ch > '9' || ch < '0'){if(ch == '-') f = -f;ch = getchar();}
    while(ch <= '9' && ch >= '0'){x = x * 10 + ch - 48;ch = getchar();}
    return x * f;
}

int n,m,x,sum,len,tot,flag,a[1000005],vis[100005];

bool cmp(int a,int b){return a > b;}

void dfs(int k, int now, int las)
{
    if(flag) return ;
    if(now == len) now = 0, k++, las = 0;
    if(k > tot)
    {
        flag = 1;
        printf("%d\n",len);
        return ;
    }
    for(re int i = las + 1; i <= n; i++)
    {
        if(vis[i]) continue;
        if(now + a[i] <= len) vis[i] = 1,dfs(k,now + a[i],i),vis[i] = 0;
        if(now == 0 || now + a[i] == len) return ;
        while(a[i + 1] == a[i]) i++;
    }
}

int main()
{
    n = read();
    while(n)
    {
        sum = 0; m = 0; flag = 0;  //初始化点题
        for(re int i = 1; i <= n; i++)
        {
            x = read();
            if(x <= 50) a[++m] = x,sum += x;
        }
        sort(a + 1, a + n + 1, cmp);
        for(re int i = a[1]; i <= sum / 2; i++)
        {
            if(sum % i != 0) continue;
            memset(vis,0,sizeof(vis));
            tot = sum / i; len = i; flag = 0;
            dfs(1,0,0); 
            if(flag) break;
        }
        if(!flag) printf("%d\n",sum);
        n = read();
    }
    return 0;
}