Luogu P1731 生日蛋糕(dfs剪枝)

#include<cstdio>
#include<cmath>
using namespace std;

int n,m,r[55],h[55],minn=0x7ffffff;

inline int min(int x,int y){return x>y?y:x;}

inline void dfs(int now,int rest,int s,int z){
    if(rest==0&&now==m+1){
        s+=r[1]*r[1];
        minn=min(minn,s);
        return;
    }
    if(rest==0||now==m+1)return;
    if(s+r[1]*r[1]>minn)return;//
    if(r[now-1]*r[now-1]*h[now-1]*z<rest)return;//
    for(int i=r[now-1]-1;i>=z;i--){
        for(int j=h[now-1]-1;j>=z;j--){
            if(i*i*j<=rest){
                r[now]=i;
                h[now]=j;
                dfs(now+1,rest-i*i*j,s+(2*i*j),z-1);
                r[now]=0;
                h[now]=0;
            }
        }
    }
}

int main(){
    /*
　　for r[1] h[1]:
    v=r*r*h
    v<n r>=m h>=m .`. r*r>=m*m 
     h=v/(r*r)  .`. h max=vmax/(r*r)min=n/(m*m)  
    r*r=v/h  .`. r*r max=vmax/hmin=n/m
　　*/
    scanf("%d%d",&n,&m);
    r[0]=int(sqrt(n/m));
    h[0]=n/(m*m);
    dfs(1,n,0,m);
    if(minn==0x7ffffff)printf("%d\n",0);
    else printf("%d\n",minn);
}