求条!DFS剪枝WA+TLE,仅30pts,玄关
查看原帖
求条!DFS剪枝WA+TLE,仅30pts,玄关
710862
thrX楼主2024/10/17 17:07

写了注释,求条

CODE:

//---------------juruo_xyu--------------------- 
#include<bits/stdc++.h>
using namespace std;
int mis[21],miv[21];//每一层的最小表面积与体积 
int h[21],r[21];
int n,m;
int sum=INT_MAX;//要求出来的 最小 表面积和 
void dfs(int s/*已经搜出来的表面积*/,int v/*已经搜出来的体积*/,int k/*第k层*/){
	if(v+miv[k]>n)return ;
	//合理化剪枝①:如果当前搜出来的体积加上剩下的最小体积 
	//(从下往上搜)还要大于n就直接结束这一个分支 
	
	if(s+mis[k]>=sum)return ;
	//合理化剪枝②:如果此时搜出来的表面积加上剩下的最小表 
	// 面积还要大于等于目前的最小表面积和 
	//就可以说再继续搜索是无意义的,直接结束该分支 
	
	//这里需要一个数学推导过程,合理化剪枝 ③ 
    //利用h与r的数组,1^^dep-1层的体积可以表示为n-v = h[k]*r[k]*r[k]   k(1---dep-1)
	//表面积为  2*h[k]*r[k] k(1---dep-1)
	//2*h[k]*r[k]=2*h[k]*r[k]*r[dep]/r[dep] >= 2*h[k]*r[k]*r[k]/r[dep] >=2*(n-v)/r[dep]
	
	//2*(n-v)/r[dep]+s>=sum
	if(s+2*(n-v)/r[k+1]>=sum){//如果当前的s加上 2*剩下的体积除以上一层的r 
		return;//直接返回 
	}
	if(k==0){//如果搜完了这一次 
		if(v==n){//如果体积符合要求 
			sum=s; //最小表面积和更新 
		}
		return ;//达到目标 
	}
	
	//开始搜索 
	for(int i=min((int)(sqrt(n-v)),r[k+1]-1);i>=k;i--){
		//上下界剪枝:
		//上界:sqrt((需要的体积-目前的体积)/h的最小值)和 
		//上一层的半径减去最小的正整数1 的最小值 
		//下界:是在每一层的最小r,在给mis miv赋值时解释过了
		//其实就是因为第一层的最小r是1,最小h是1
		//往下每一层就是各自+1 
		//注意:(需要的体积-目前的体积)/h的最小值 是为了 
		//算出r的平方,并且min()是因为两者都有可能超出了 
		//需要的值(后者超出的时候大概只会在第M层的时候 
		//出现),而定然也只会有一个超出,所以要取min() 
		for(int j=min((int)((n-v)/(i*i)),h[k+1]-1);j>=k;j--){
			//还是上下界剪枝
			//上界:懒得写了 
			//i是前面的半径 
			//解释: 前者算出h,后者是上一层的h -1 
			//下界:k   
			r[k]=i;//对r的第k层进行赋值 
			h[k]=j;//对h的第k层进行赋值
			//万一这个值“不合格”
			//其实 DUCK不必 因为最后总会被覆盖掉的
			int temp=0;//底面积临时变量  
			if(k==1){
				temp=r[m]*r[m];//底面积 
			}
			dfs(s+temp+2*i*j,v+i*i*j,k-1); 
		} 
	}
	 
} 
int main(){
	
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0); 
	//先关闭同步流 
	cin>>n>>m; 
	mis[0]=0;//虚拟层,第一层顶上的那一层 
	miv[0]=0;
	for(int i=1;i<=m;i++){
		//因为第i层的最小r和最小h都是1
		mis[i]=mis[i-1]+2*i*i;//其实是侧面积,因为最后只需要加上最底层的底面积就好了 
		miv[i]=mis[i-1]+i*i*i;//最小体积 
	}
	h[m+1]=1e9+7;
	r[m+1]=1e9+7;
	//防止最下面的虚拟层第m+1层比第m层小 
	dfs(0,0,m);
	cout<<sum<<'\n';

	return 0;
} 
2024/10/17 17:07
加载中...