1、B站视频链接：B21 DFS剪枝 分成互质组_哔哩哔哩_bilibili

#include  
using namespace std;
const int N=11;
int n,a[N],ans=N,cnt;
vector g[N];
int gcd(int x,int y){
	return y?gcd(y,x%y):x;
}
bool check(int x,int i){
	for(int j=0;j1)return false;
	}
	return true;
}
void dfs(int u){
	if(cnt>=ans)return;//剪枝
	if(u==n){//边界 
		ans=cnt;
		return;
	}
	for(int i=0;i 
2、B站视频链接：B22 DFS剪枝 小猫爬山_哔哩哔哩_bilibili
 
题目链接：
 
 
#include  
using namespace std;
const int N=30;
int n,w,ans=N,cnt;
int c[N],sum[N];
void dfs(int u){
	if(cnt>=ans)return;//最优剪枝
	if(u==n){
		ans=cnt;
		return ;//边界 
	} 
	for(int i=0;i>n>>w;
	for(int i=0;i>c[i];
	sort(c,c+n);
	reverse(c,c+n);//从大的开始 
	dfs(0);
	cout<
 
3、B站视频链接：B23 DFS剪枝 小木棍_哔哩哔哩_bilibili
 
题目链接：小木棍 - 洛谷
 
 
 
 
 
#include  
using namespace std;
const int N=70;
int n,len,cnt;
int a[N],used[N];
//当前拼接第u根原始木棍，已拼接的长度为cur，
//下一段开始拼接的小木棍为start
void dfs(int u,int cur,int start){
	if(u>cnt){
		printf("%d",len);exit(0);//拼好全部，立即退出 
	}
	if(cur==len){
		dfs(u+1,0,1);
		return;//拼好第u根，再拼下一根 
	}
	for(int i=start;i<=n;i++){
		if(used[i]||cur+a[i]>len)continue;//不合法就跳过
		used[i]=1;
		dfs(u,cur+a[i],i+1);
		used[i]=0;//拼接a[i]失败，恢复现场，在尝试a[i+1]
		
		if(cur==0)return;//cut1拼接第一个，失败回溯
		if(cur+a[i]==len)return;//cut2拼接最后一个，失败回溯
		while(i>n;int sum=0;
	for(int i=1;i<=n;i++){
		cin>>a[i],sum+=a[i];
	}
	sort(a+1,a+1+n);reverse(a+1,a+1+n);//从小到大
	for(len=a[1];;len++){
		if(sum%len)continue;//不等于0不合法就跳过
		cnt=sum/len;
		dfs(1,0,1);//第一次拼好即为答案 
	} 
	
	return 0;
}
 
4、B站视频链接：B24 DFS剪枝 生日蛋糕_哔哩哔哩_bilibili
 
题目链接：[NOI1999] 生日蛋糕 - 洛谷
 
 
 
#include  
using namespace std;
const int N=20,INF=1e9;
int n,m,ans=INF;
int minv[N],mins[N];
//当前层是第u层，第u+1层的半径为R、高度为H
//m~u+1层的体积和为v、面积和为s
void dfs(int u,int R,int H,int v,int s){
  if(u==0){if(v==n)ans=min(ans,s); return;} //边界
  if(v+minv[u]>n) return;      //cut3:体积和越界
  if(s+mins[u]>=ans) return;   //cut4:面积和更差
  if(s+2*(n-v)/R>=ans) return; //cut5:估价不等式
  for(int r=min(R-1,(int)sqrt(n-v));r>=u;r--)
    for(int h=min(H-1,(n-v)/(r*r));h>=u;h--)//cut1+cut2
      dfs(u-1,r,h,v+r*r*h,s+2*r*h+(u==m?r*r:0));
}
int main(){
  cin>>n>>m; //体积n 层数m
  for(int i=1; i<=m; i++){
    minv[i]=minv[i-1]+i*i*i; //1~i层的最小体积和
    mins[i]=mins[i-1]+2*i*i; //1~i层的最小侧面积和
  }
  dfs(m,INF,INF,0,0); //cut1:优化搜索顺序，从大到小
  if(ans==INF) ans=0; 
  cout<
 
 
 
 
 
 遵义网站建设  安卓开发工具有哪些  天津做网站的网络公司  深圳网站建设手机版  查排名的网站  苏州公司建站模板