题解 P1120 【小木棍 ［数据加强版］】

· · 题解

{\color{orange}\text{欢迎拜访我这个蒟蒻的博客}}

P1120 【小木棍 ［数据加强版］】传送门

此题算法:暴搜

由于错误思想太多了，题解只讲正确算法

1.输入木棍长度，算出合法木棍的数量t，长度和sum，长度最大值maxn，并将木棍桶排序。

2.枚举长木棍长度len，tot表示拼成的长木棍数量。然后dfs，四个参数中k表示拼到第几根长木棍，rest表示当前拼的长木棍剩余需拼长度，lon表示拼一个新长木棍时枚举最长的小木棍长度，st表示在拼某一个长木棍时依次枚举的小木棍长度。

3.如文中剪枝，dfs的返回值是方案是否可行，第一个可行的方案中，len就是答案。

以下是代码

#include <bits/stdc++.h>
using namespace std;
int n,in[70],maxn;
int t,a[70],sum,ans;
int num[70],len,tot;
inline int read(){
    int f=1,dig=0;
    char ch=getchar();
    while(ch<'0'||ch>'9'){
        if(ch=='-') f=-1; 
        ch=getchar();
    } while(ch>='0'&&ch<='9'){
        dig=(dig<<3)+(dig<<1)+ch-'0';
        ch=getchar();
    } return f*dig;
} 
//lon表示：每次要拼一个新的长木棍时，
//枚举的最长的小木棍的长度
//（显然，这个值是非递增的，每次向下枚举） 
//st表示：在拼某一个长木棍时，依次枚举的小木棍长度。
//（这个也是非递增的，每次可以从start向下枚举）。 
bool dfs(int k,int rest,int lon,int st){
    if(k==tot+1) return 1;
    if(!rest) return dfs
        (k+1,len,lon,lon);
    st=min(st,rest);
    for(int now=st;now;now--)
        if(num[now]){
            num[now]--;
            int tmp;
            if(len==rest)
                tmp=now;
            else tmp=lon;
            if(dfs(k,rest-now,tmp,now))
                return 1;
            //如果Len==rest，代表这是这根长木棍第一次拼，更新一下longest的值。 
            num[now]++;
            if(len==rest) break; 
            /*这个表示长木棍是第一次拼。 
            注意，目前这根短木棍now最终必然会属于一个长木棍。
            如果第一次拼时不合法，说明这根短木棍所在的长木棍无法被拼出，可以直接结束 。*/ 
            if(now==rest) break;
            /*如果现在剩下rest，而且刚好有一根长度为rest的木棍，我肯定选它最优；
            所以，如果试了它发现不成功，一定不会成功。*/
        }
    return 0;
} int main(){
//  freopen("1120.in","r",stdin);
    n=read();
    for(int i=1;i<=n;i++){
        in[i]=read();
        if(in[i]<=50){
            a[++t]=in[i];
            sum+=a[t];
            maxn=max(maxn,a[t]);
        }
    } if(!t){
        printf("0\n");
        return 0;
    } for(int i=1;i<=t;i++)
        num[a[i]]++;
    for(int i=maxn;i<=sum;i++){
        if(sum%i>0)
            continue;
        len=i; tot=sum/i;
        if(dfs(1,len,maxn,maxn)){
            ans=i;
            break;
        }
    } printf("%d\n",ans);
    return 0;
}
谢谢大家! !