poj1190 生日蛋糕 dfs

題意：生日蛋糕有m層，總體積是V。從下向上，每一層的半徑r和高度h都是遞減的。

給m、v，求最小的表面積s。（不算底面接地的面積）

題目鏈接：poj1190

剪枝都還沒加。。樣例輸出都是錯的。。。還沒找到問題。。。

#include <iostream>
#include <cstring>
#include <string>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <vector>
#include <map>
#define inf 0x3f3f3f3f
using namespace std;

int ans,V,M,flag,s;

int dfs(int v,int m,int newr,int newh)
{
    int r,h,tmp,i;
    if(m==0)
    {
        flag=1;
        if(v==0&&s<ans) ans=s;
        return 0;
    }
    for(i=1,tmp=0;i<=m;i++)//若之後每層都取最小值
        tmp+=(i*i*i);
    if(tmp>v) return 0;//依然大於剩余的v 那麼一定不可能
    tmp-=(m*m*m);
    for(r=newr;r>=m;r--)
    {
        for(h=newh;h>=m;h--)
        {
            //for(i=0,tmp=0;i<m;i++)//每層取最大值  //這個剪枝加了也有問題
            //    tmp+=(r-i)*(r-i)*(h-i);
            //if(v>tmp) break;//依然小於v 也不可能
            if(m==M) s+=r*(2*h+r);
            else s+=2*r*(h+r);
            if(s<ans) dfs((v-(r*r*h)),m-1,r-1,h-1);
            if(m==M) s-=r*(2*h+r);
            else s-=2*r*(h+r);
        }
    }
    return 0;
}

int main()
{
    while(~scanf("%d%d",&V,&M))
    {
        ans=inf;
        s=0;
        flag=0;
        dfs(V,M,1000,1000);
        printf("%d\n",flag?ans:0);
    }
    return 0;
}