小木棍

进阶指南P102

#include<bits/stdc++.h>
using namespace std;

int m,sum,n,a[70],tmp[70],len,cnt,ans,mt,y;

bool dfs(int now,int l,int last){
    if (now>cnt) return 1;
    if (l==len) return dfs(now+1,0,1);
    int ch=0;
    for (int i=last;i<=n;++i){
        if (!tmp[i] && l+a[i]<=len && ch!=a[i]){
            tmp[i]=1;
            if (dfs(now,l+a[i],i+1)) return 1;
            tmp[i]=0;
            ch=a[i];
            if (l==0 || l+a[i]==len) return 0;
        }
    }
    return 0;
}

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

void solve(){
    sum=n=mt=0;
    for (int i=1;i<=m;++i){
        int tmp;
        scanf("%d",&tmp);
        if (tmp<=50){
            n++;
            a[n]=tmp;
            sum+=tmp;
            mt=max(mt,tmp);
        }
    }
    sort(a+1,a+n+1,cmp);
    memset(tmp,0,sizeof(tmp));
    for (int i=mt;i<=sum;++i){
        if (sum%i==0){
            len=i;
            cnt=sum/len;
            if (dfs(1,0,1)){
                cout<<i<<endl;
                return;
            }
        }
    }
}

int main(){
    while (scanf("%d",&m)!=EOF){
        if (m==0) return 0;
        solve();
    }
    return 0;
}

生日蛋糕

进阶指南P105

#include <bits/stdc++.h>
using namespace std;

int minv[25],mint=1e9,m,v;

int maxv(int n,int r,int h){
    int ret=0,i;
    for (i=n,r--,h--;i<=m;++i,r--,h--){
        ret+=r*r*h;
        if (ret>=10000||r*r*h>=10000) return 10000;
    }
    return ret;
}

void dfs(int n,int lr,int lh,int nv,int ns){
    if (ns>=mint) return;
    else if(nv+minv[m-n+1]>v) return;
    else if(nv+maxv(n,lr,lh)<v) return;
    if (n==m){
        for (int r=lr-1;r>=1;--r){
            if ((v-nv)%(r*r)) continue;
            else{
                int tmp=(v-nv)/(r*r);
                if (tmp<lh){
                    int tt=ns+2*r*tmp;
                    if (m==1) tt+=r*r;
                    mint=min(mint,tt);
                }
            }
        }
        return;
    }
    for (int r=lr-1;r>=m-n+1;--r){
        for (int h=min(lh-1,(int)((v-nv)/(r*r)));h>=m-n+1;--h){
            if (n==1) dfs(2,r,h,r*r*h,r*r+r*h*2);
            else dfs(n+1,r,h,nv+r*r*h,ns+2*r*h);
        }
    }
}

int main(){
    cin>>v>>m;
    for (int i=1;i<=m;++i){
        minv[i]=minv[i-1]+i*i*i;
    }
    dfs(1,sqrt(v),v,0,0);
    cout<<mint<<endl;
    return 0;
}

本作品采用知识共享署名-非商业性使用-相同方式共享 3.0 未本地化版本许可协议进行许可。
本文链接：https://hs-blog.axell.top/archives/88/