分析:很巧妙的在于,先设计一个最小的蛋糕,这样v和s的下界就都有了!然后有两个估计数值:

半径区间:rl1-1>=rl>=l
高度区间:min{hl1-1, vl1-fv[l-1]/(rl*rl)}>=hl>=l

然后有三个剪刀条件:1.体积:估计最小体积>=剩余体积;2.表面积:剩余最小面积sv[l-1]+已有面积<best;

3.这个比较好耍,LeftS=sum(i:l-1->1)2RiHi>=2(LeftV)/Rl,假设2(LeftV)/Rl>=best-已有面积,那我们有LeftS>=best-已有面积,换句话说,下界不可能达到best,所以对与2LeftV>=LeftS*Rl,我们也要直接剪掉!

做题的时候,居然忘记料变量循环,将所有值累计起来,sigh!很让我郁闷!太低级的错误了!还有就是,剩余体积要为0,今天怎么都犯这种错误哟,失败!

Source Code

Problem: 1190

User: orlando22

Memory: 288K

Time: 219MS

Language: C++

Result: Accepted
  • Source Code
    #include <iostream>
    #include <math.h>
    
    using namespace std;
    
    const int MAXEL=20;
    long v, fv[MAXEL], sv[MAXEL];//lower boundary for v and s
    int m;
    //variables for best
    long best;
    
    //declaration
    void cake(int l, long vl1, long hl1, long rl1, long sl1);
    void precal(int m);//using m to calculate
    long allfV(long rl, long hl, int l);
    
    //implementation
    void precal(int m){
        fv[1]=sv[1]=1;
        for(int i=2; i<=m; i++){
            fv[i]=fv[i-1]+i*i*i;
            sv[i]=sv[i-1]+2*i*i;
        }
    }
    
    long allfV(long rl, long hl, int l){
        long sum=0;
        for(long k=0; k<l; k++){
            sum+=(rl-k)*(rl-k)*(hl-k);//rl,hl->rl-l+1,hl-l+1
        }
        return sum;
    }
    
    void cake(int l, long vl1, long hl1, long rl1, long sl1){
        if(l==0){
            if(sl1<best&&vl1==0) best=sl1;//sigh!
            return;
        }
        //rl1-1>=rl>=l
        for(long rl=l; rl<=rl1-1; rl++){
            //min{hl1-1, vl1-fv[l-1]/(rl*rl)}>=hl>=l
            long upper_hl=(vl1-fv[l-1])/(rl*rl);
            if(hl1-1<upper_hl) upper_hl=hl1-1;
            //intial value
            if(l==m) sl1=rl*rl;//take care of  here!
            for(long hl=l; hl<=upper_hl; hl++){
                //mini-V>=vl1,sl1+sv[l-1]<best
                //(best-sl1)*rl>=2*(vl1-rl*rl*hl)
                long minV=allfV(rl, hl, l),leftV=vl1-rl*rl*hl,cS=sl1+2*rl*hl;//using local copy, don't recovery!
                if(minV>=vl1&&cS+sv[l-1]<best&&(2*leftV/rl)+cS<best){
                    cake(l-1, leftV, hl, rl, cS);
                }
            }
        }
    }
    
    int main()
    {
        //implementation
        cin>>v,cin>>m;
        precal(m);
        //reset best
        best=LONG_MAX;
        cake(m, v, v+1, (long)sqrt((float)v)+1, 0);
    
        if(best==LONG_MAX) cout<<0<<endl;
        else cout<<best<<endl;
    
        return 0;
    }
    

Advertisements