搜索+剪枝,主要考察细节和搜索的顺序,首先可以发现所有数据均为整数,所以初始化每层的蛋糕R和H是整数,然后从高层向低层搜索,然后预处理出各层向低层的最小面积和体积用来剪枝。

就可以每层从当前最大半径向最小半径枚举,并分类讨论加剪枝即可。

#include <bits/stdc++.h>
using namespace std;
int n, m, S[1001], V[1001];//最小面积和体积
struct cak {
int R, H, CS, S, V;
}data[1001];
int minn = 2147483647;
void dfs(int now, int nS, int nV, int R, int H)//now层数,nS当前蛋糕面积,nV当前蛋糕体积,R最大半径,H最大高度
{
if (now == 0)
{
if (nV == n)
minn = min(minn, nS);
return;
}
if (nS + S[now - 1] > minn) return;//如果当前的蛋糕面积加上最小的面积大于minn
if (nV + V[now - 1] > n) return;//如果当前的蛋糕体积加上最小的体积比n大。
if (2 * (n - nV) / R + nS >= minn) return;//如果当前体积所换算成的面积大于minn
for (int i = R; i >= data[now].R; i--)//i一定比data[now].R
{
if ( now == m )
nS = i * i;
int tot = min( H, (n - (nV + V[now - 1])) / (i * i) );//tot是接下来要取到的h的最小值,
for (int j = tot; j >= data[now].H; j--)
dfs(now - 1, nS + 2 * i * j, nV + i * i * j, i - 1, j - 1);
}
}
inline void init()
{
scanf("%d%d", &n, &m);
for (int i = 1; i <= m; i++)
data[i].R = i, data[i].H = i, data[i].CS = data[i].H * data[i].R * 2, data[i].S = data[i].R * data[i].R, data[i].V = data[i].S * data[i].H;
for (int i = 1; i <= m; i++)
S[i] = S[i - 1] + data[i].CS, V[i] = V[i - 1] + data[i].V;
}
int main()
{
init();
dfs(m, 0, 0, 25, 25);
if (minn == 2147483647) printf("0");
else printf("%d", minn);
return 0;
}
05-18 07:55