题解 P1731 【生日蛋糕】

Victorique · 2017-08-11 08:51:11 · 题解

看了楼下那么多代码，优化的方法比较一致，其实这个题还有一些其他的优化方法。

比如搜索时把高倒过来搜，由于数学规律，会比正着搜快。

下面是代码：

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<string>//蒟蒻的我一直担心头文件不够用。。
using namespace std;
int minn=10000000,p,q,n,m,mj,tj;//minn来储存最优解，由于需要存放最小值，所以定的大。
int vmin[1001],smin[1001];
void search(int,int,int,int,int);
int main()
{
    //freopen("cake.in","r",stdin);
    //freopen("cake.out","w",stdout);请无视掉这两行。。。。。
    cin>>n>>m;
    smin[m+1]=0;
    vmin[m+1]=0;
    for(int i=1;i<=m;i++)
    {
        smin[m-i+1]=smin[m-i+2]+2*i*i;
        vmin[m-i+1]=vmin[m-i+2]+i*i*i;//存入每一层可能得到的最优解，为后面剪枝做准备。
    }
    search(1,sqrt((n-vmin[2])/m)+1,(n-vmin[2])/m/m+1,0,0);第一次进入搜索时为了确定最优的边界，用sqrt((n-vmin[2])/m)+1求出可能得到的最大的半径，用(n-vmin[2])/m/m+1求出可能得到的最大的高，提高部分效率。
    cout<<minn;
}
void search(int i,int ri,int hi,int s,int v)
{
    int r,h,vmax,j;
    for(r=m-i+1;r<=ri-1;r++)
     {
        if (i==1)
         s=r*r;//数学好的都能算出来，无论这个蛋糕长啥样表面积都会是最下层的底面积加上n层的侧面积。。。
         for(h=hi-1;h>=m-i+1;h--)//优化，据大佬说，高的变化是线性的，从大到小搜索高的值要比从小到大快的多。
         {
         if (s+2*r*h+smin[i+1]<minn&&(v+r*r*h+vmin[i+1])<=n&&(v+r*r*h+(r-1)*(r-1)*(m-i)*(h-1))>=n)//剪枝，楼下的都已经说过了原因，这里不再写。最后一个判断条件代表当前一层之上的所有层能有的一个最大的体积。
         {
             if (i==m)
             minn=s+2*r*h;//如果已经找到了最上层，保存最优值。
             else
             search(i+1,r,h,s+r*h*2,v+r*r*h);//递归搜索
         }
         }
     }
}