求条,剪枝wa了
查看原帖
求条,剪枝wa了
1381314
hapihapi楼主2024/8/29 13:34
#include<bits/stdc++.h>
using namespace std;
int n,m;
int mis[17],miv[17];
int ans=INT_MAX;
void dfs(int dep,int r,int h,int v,int s){
	if(dep>m){
		if(v==0&&ans>s){
			ans=s;
		}
		return;
	}
	if(v-miv[dep]<0||s+mis[dep]>=ans) return;
	for(int i=r-1;i>=m-dep+1;i--){
		if(dep==1) s=i*i;
		if(2*v/i+s>=ans) break;
		for(int j=min(h-1,(v-miv[dep+1])/(i*i));j>=m-dep+1;j--){
			dfs(dep+1,i,j,v-i*i*j,s+2*i*j);
		}
	}
}
int main(){
	cin>>n>>m;
	for(int i=m;i>=1;i--){
		mis[i]=(m+1-i)*(m+1-i)*2+mis[i+1];//第i层后最小表面积 (包括i) 
		miv[i]=(m+1-i)*(m+1-i)*(m+1-i)+mis[i+1];// //第i层后最小体积 (包括i)
	}
	dfs(1,sqrt(n),sqrt(n),n,0);//层数,半径,高度,体积,表面积 
	if(ans!=INT_MAX)cout<<ans;
	else cout<<0;
	return 0;
}

我这是剪枝剪错了吗,除了前三个点都wa了

2024/8/29 13:34
加载中...