题解 P1731 【生日蛋糕】

cyborg · 2017-12-09 09:26:48 · 题解

首先确定半径和高的最大值，20000的三次方约等28，也就是说半径和高最大能取到28了，如楼下所说，要剪枝。

当前体积大于目前答案时剪枝不多说。

当前层数y之后最小表面积等于1^3+2^3+...+（y-1）^3，我们可以存个数组。

而萌新表示看不懂是怎么求最大体积，所以想到了用数组maxv[r][h]（r>h（r<=h同理）不管层数）表示1^2*(h-r+1)+2^2*(h-r+2)+...+(r-1)^2*(h-1).

假设是是从上往下（注意！）数第y层，设定半径为r，高为h，之后的最大体积就等于(r-y)^2*(h-y)+(r-y+1)^2*(h-y+1)+...+(r-1)^2*(h-1).就可以表示为maxv[r-1][h-1]-maxv[r-y][h-y]。

至于maxv[r][h]=maxv[r-1][h-1]+r*r*t，所以一个28*28次的循环就够了。代码如下：

#include<cstdio>
#include<iostream>
#include<cmath>
using namespace std;
int ans=100000,minv[16],maxv[29][29];
void dfs(int y,int v,int s,int r,int h)//y是还有多少层要铺，v是已求表面积，s是剩余体积，r、h是上一层的高 
{
    //cout<<y<<' '<<v<<' '<<s<<' '<<r<<' '<<h<<endl;
    if(s>=ans)return ;                //表面积大于已求答案 
    if(v==0&&y==0)ans=s;            //判断，存答案 
    if(v==0||y==0)return ;
    for(int i=y;i<r&&v-i*i>=minv[y-1];i++)        //i求半径 ，h求高 
    for(int t=y;t<h;t++)
    {
        if(s>=ans)return ;                        //判断表面积 
        if(v-t*i*i<minv[y-1])break;                //判断最小体积 
        if(maxv[i-1][t-1]-maxv[i-y][t-y]<v-i*i*t)continue;//判断最大体积 
        if(s!=0)dfs(y-1,v-i*i*t,s+2*i*t,i,t);else
        dfs(y-1,v-i*i*t,i*i+2*i*t,i,t);            //铺最下面一层时加上俯视图的面积 
    }
}
int main()
{
    int i,t;
    for(i=1;i<=15;i++)
    minv[i]=minv[i-1]+i*i*i;        //minv[i]=1^3+2^3+...+i^3，minv[y]表示（从上往下数 ）1到y-1层最小体积 
    for(i=1;i<=28;i++)
    for(t=1;t<=28;t++)
    {
        maxv[i][t]=maxv[i-1][t-1]+i*i*t;//1^2*(h-r+1)+2^2*(h-r+2)+...+(r-1)^2*(h-1)，maxv[r-1][h-1]-maxv[r-y][h-y]表示（从上往下数）1到y-1层当y层半径r，高h时的最大体积 
    }
    int n,m;
    cin>>n>>m;
    dfs(m,n,0,28,28);
    cout<<ans;
}