luogu1731生日蛋糕 搜索剪枝

传送门

https://www.luogu.org/problemnew/show/P1731

思路

1. 就是单纯的搜索加剪枝
2. 剪枝1：上下界剪枝，每一层的上界是上一层的r,h -1。下界是dep。第m层的r和h最小分别是sqrt(n)+1
3. 最优性剪枝和可行性剪枝
   
   

code

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<cmath>
#include<cstdlib>
#include<ctime>
using namespace std;
typedef long long ll;
const int inf=0x3f3f3f3f;
inline int read(){
	char ch=' ';int f=1;int x=0;
	while(ch<'0'||ch>'9'){if(ch=='-') f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
	return x*f;
}
const int M=20;
int minv[M];
int mins[M];
int r[M],h[M];
int anss=inf;
int n,m;
void dfs(int dep,int s,int v)
{
	if(v+minv[dep]>n) return ;
	if(s+mins[dep]+r[m]*r[m]>anss) return ;
	if(s+2*(n-v)/r[dep+1]+r[m]*r[m]>anss) return ;
	if(dep==0)
	{
		if(v==n)
		{
			anss=min(anss,s+r[m]*r[m]);
		}
		return ;
	}
	for(int cr=r[dep+1]-1;cr>=dep;cr--)
	{
		for(int ch=h[dep+1]-1;ch>=dep;ch--)
		{
			r[dep]=cr;
			h[dep]=ch;
			dfs(dep-1,s+2*cr*ch,v+cr*cr*ch);
			r[dep]=0;
			h[dep]=0;
		}
	}
}
int main()
{
	
	n=read(),m=read();
	int i,j;
	for(i=1;i<=m;i++)
	{
		minv[i]=minv[i-1]+i*i*i;
		mins[i]=mins[i-1]+2*i*i;
	}
	r[m+1]=sqrt(n)+1;
	h[m+1]=sqrt(n)+1;
	dfs(m,0,0);
	cout<<anss<<endl;
	return 0;
}