【玄关】如果使用朴素dfs不加剪枝求调
查看原帖
【玄关】如果使用朴素dfs不加剪枝求调
1038710
AutumnQ楼主2024/6/28 19:15

我知道需要使用剪枝,但如果写部分分代码我有点问题

#include<bits/stdc++.h>
using namespace std;
int r[11120],h[11120];
int n,c;
int ans=2147483647;
void dfs(int f,int cost,int s){
	if(f==n+1){
		if(s==c)ans=min(ans,cost);
		return;
	}
	if(f==n){
		for(int i=1;i<=r[f-1];i++){
			int h1=(c-s)/i/i;
			if(h1*i*i!=(c-s) || h1<=0 || h1>=h[n-1])return;
			else h[n]=h1,r[n]=i,dfs(f+1,cost+2*i*h1,s+h1*i*i);
		}
		return;
	}
	for(int i=r[f-1]-1;i>=1;i--){
		for(int j=h[f-1]-1;j>=1;j--){
			if(i*i*j<(c-s)){
				r[f]=i,h[f]=j;
				dfs(f+1,cost+2*i*j,s+i*i*j);
			}
		}
	}
}
int main(){
	cin>>c>>n;
	for(int i=1;i*i<=c;i++){
		for(int j=1;j*j<=c;j++){
			if(i*i*j>c)break;
			else h[1]=j,r[1]=i,dfs(2,i*i+2*i*j,i*i*j);
		}
	}
	if(ans==2147483647)puts("0");
	else cout<<ans;
}
2024/6/28 19:15
加载中...