NOI1999 生日蛋糕

#include<iostream>

#include<cstdio>

#include<cmath>

using namespace std;

#define INF 0x3f3f3f3f

#define N 20010

int n,m;

int ans=INF;

int r[N],h[N];

void dfs(int k,int v,int s,int p){

    if(s>=ans)

        return ;

    if(k-1>m)

        return ;

    if(v>n)

        return ;

    if(v==n && k-1==m){

        s+=r[1]*r[1];

        ans=min(ans,s);

        return ;

    }

    if(s+r[1]*r[1]+p>ans)

        return ;

    if(v+r[k-1]*r[k-1]*h[k-1]*p<n)

        return ;

    for(int i=r[k-1]-1;i>=p;i--)

        for(int j=h[k-1]-1;j>=p;j--)

            if(v+i*i*j<=n && k<=m){

                r[k]=i;

                h[k]=j;

                dfs(k+1,v+i*i*j,s+i*j*2,p-1);

                r[k]=0;

                h[k]=0;

            }

}

int main(){

    scanf("%d%d",&n,&m);

    r[0]=h[0]=sqrt(n);

    dfs(1,0,0,m);

    if(ans==INF)

        printf("0");

    else printf("%d",ans);

    return 0;

}
巴特西

NOI1999 生日蛋糕

最新文章

热门文章
