【NOI1999、LOJ#10019】生日蛋糕(搜索、最优化剪枝、可行性剪枝)

主要是剪枝的问题，见代码，讲的很详细

#include<iostream>

#include<cstdio>

#include<cmath>

#include<algorithm>

using namespace std;

inline int read(){

	char chr = getchar();	int f = 1,ans = 0;

	while(!isdigit(chr)) {if(chr == '-') f = -1;chr = getchar();}

	while(isdigit(chr))  {ans = (ans << 3) + (ans << 1);ans += chr - '0';chr = getchar();}

	return ans* f ;

}

void write(int x){

	if(x < 0) putchar('-'),x = -x;

	if(x > 9) write(x / 10);

	putchar(x % 10 + '0');

}

int r[50],h[50];//上一次的半径、高

int N,M;

int ans=0x3f3f3f3f;

void dfs(int x,int V,int S,int kk){//当前第x层,当前总共体积为V，当前总侧面积为S，还有kk层没有处理

	if(S+r[1]*r[1]+kk>=ans) return;//最优化剪枝，如果当前总侧面积+底面积（三视图角度理解）>=当前记录的答案

	if(x>M+1) return;//超出M层

	if(N-V-r[x-1]*r[x-1]*h[x-1]*kk>0) return;//同上最优化剪枝,（假设之后每一层的底面积都是上一层的半径与高）

	if(V==N && x==M+1){//如果可以记录进答案

		ans=min(ans,S+r[1]*r[1]);

		return;

	}

	for(int H=h[x-1]-1;H>=kk;H--)

	for(int R=r[x-1]-1;R>=kk;R--){//枚举L,R,（上下界剪枝）

		h[x]=H;

		r[x]=R;

		V+=r[x]*r[x]*h[x];

		S+=2*r[x]*h[x];

		dfs(x+1,V,S,kk-1);

		V-=r[x]*r[x]*h[x];

		S-=2*r[x]*h[x];//回溯

	}

}

int main(){

	N=read(),M=read();

	h[0]=(int)sqrt(N);

	r[0]=(int)sqrt(N);

	dfs(1,0,0,M);

	if(ans==0x3f3f3f3f)

		cout<<-1;//答案没有更新过的话，输出-1

	else

		cout<<ans;

	return 0;

}