AcWing 167. 木棒
dfs+剪枝:
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int N=70;
int n,a[N],flag[N],sum,len;
//a:每个木棍长度,flag:状态数组
//len:木棒的长度,sum:所有木棍的总长度
//cnt:当前正在拼第几根木棒,curlen:当前木棒中已拼木棍的总长度,start:从哪个位置开始枚举木棍
bool dfs(int cnt,int curlen,int start){
//木棒数量*木棒长度==所有木棍的总长度,找到答案
if(cnt*len==sum) return true;
//当前木棒已被木棍拼好,dfs下一木棒
if(curlen==len) return dfs(cnt+1,0,0);
//剪枝2:排除冗余:递增枚举木棍的编号
for(int i=start;i<n;i++){
//如果当前木棍用过了,则跳过
if(flag[i]) continue;
//如果当前木棍拼上该长度没超过len,继续dfs
if(curlen+a[i]<=len){
flag[i]=true;//标记选中
if(dfs(cnt,curlen+a[i],i+1)) return true;
flag[i]=false;//回溯
//到此为当前木棍搜索失败
//剪枝3:如果第一根木棍或者最后一根木棍搜索失败,则一定搜不到方案
if(!curlen||a[i]+curlen==len) return false;
//剪枝4:如果当前木棍没有搜到方案,则跳过所有长度相等的木棍
int j=i;
while(j<n&&a[j]==a[i]) j++;
i=j-1;
}
}
return false;
}
int main(){
//多组测试数据直至0截止输入
while(cin>>n,n){
//清空数组a,flag
memset(a,0,sizeof a);
memset(flag,0,sizeof flag);
//初始化更新sum,len
sum=0,len=0;
//求出sum,len(>=数组a中的max)
for(int i=0;i<n;i++){
cin>>a[i];
sum+=a[i];
len=max(len,a[i]);
}
//剪枝1:优化搜索顺序,木棍长度从大到小排序
sort(a,a+n,greater<int>());
//循环一定会退出,最坏情况下所有木棍拼一根木棒
while(true){
//找到答案
if(sum%len==0&&dfs(0,0,0)){
cout<<len<<endl;
break;
}
//没找到答案,len自增
len++;
}
}
return 0;
}
AcWing 843. n-皇后问题
dfs每一行:
#include<iostream>
using namespace std;
const int N=10;
int n;
char mapp[N][N];
bool col[N],dg[2*N],udg[2*N];
//col:列,dg:主对角线(y=x+b)->(b=y-x)->(b=y-x+n),udg:反对角线(y=-x+b)->(b=x+y)
void dfs(int row){//row:行
if(row==n+1){
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
cout<<mapp[i][j];
}
cout<<endl;
}
cout<<endl;
return ;
}
for(int i=1;i<=n;i++){//枚举全部的列
if(!col[i]&&!dg[n-row+i]&&!udg[row+i]){
mapp[row][i]='Q';
col[i]=dg[n-row+i]=udg[row+i]=true;
dfs(row+1);
col[i]=dg[n-row+i]=udg[row+i]=false;
mapp[row][i]='.';
}
}
return ;
}
int main(){
cin>>n;
for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) mapp[i][j]='.';
dfs(1);
return 0;
}
dfs每一个格子:
#include<iostream>
using namespace std;
const int N=10;
int n;
char mapp[N][N];
bool row[N],col[N],dg[2*N],udg[2*N];
//row:行,col:列,dg:主对角线(y=x+b)->(b=y-x)->(b=y-x+n),udg:反对角线(y=-x+b)->(b=x+y)
void show(){
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
cout<<mapp[i][j];
}
cout<<endl;
}
cout<<endl;
}
void dfs(int x,int y,int cnt){
if(y==n+1) x++,y=1;
if(x==n+1){
if(cnt==n){
show();
}
return ;
}
//不放皇后
dfs(x,y+1,cnt);
//放皇后
if(!row[x]&&!col[y]&&!dg[n+y-x]&&!udg[x+y]){
mapp[x][y]='Q';
row[x]=col[y]=dg[n+y-x]=udg[x+y]=true;
dfs(x,y+1,cnt+1);
row[x]=col[y]=dg[n+y-x]=udg[x+y]=false;
mapp[x][y]='.';
}
return ;
}
int main(){
cin>>n;
for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) mapp[i][j]='.';
dfs(1,1,0);
return 0;
}
AcWing 1243. 糖果(第十届省赛)
暴力dfs (超时未AC 50points):
#include<iostream>
#include<cstring>
using namespace std;
const int N=10;
int n,m,k;
int a[105][25],flag[25];
bool row[105],key;
bool check(){
for(int i=1;i<=n;i++){
if(row[i]){
for(int j=1;j<=k;j++){
flag[a[i][j]]++;
}
}
}
for(int i=1;i<=m;i++) if(flag[i]==0) return false;
return true;
}
void dfs(int x,int cnt,int sum){
if(cnt==sum){
if(check()){
cout<<sum<<endl;
key=true;
}
memset(flag,0,sizeof flag);
return ;
}
for(int i=x;i<=n;i++){
if(!row[i]){
row[i]=true;
dfs(x+1,cnt+1,sum);
if(key) return ;
row[i]=false;
}
}
return ;
}
int main(){
cin>>n>>m>>k;
for(int i=1;i<=n;i++) for(int j=1;j<=k;j++) cin>>a[i][j];
for(int i=(m/k)+(bool)(m%k);i<=n;i++){
memset(row,0,sizeof row);
memset(flag,0,sizeof flag);
dfs(1,0,i);
if(key) break;
}
if(!key) cout<<"-1"<<endl;
return 0;
}
AcWing 4957. 飞机降落(第十四届省赛)
dfs(AC):
注意:dfs代码中,取较大值这个细节:
max(alltime,timee[i].startt)+timee[i].needd
#include<iostream>
#include<cstring>
using namespace std;
int T,n;
bool flag[12],key;
struct TIME{
int startt,lastt,needd;
}timee[12];
void dfs(int cnt,int alltime){
if(cnt==n){
key=true;
return ;
}
for(int i=1;i<=n;i++){
if(!flag[i]&&alltime<=timee[i].startt+timee[i].lastt){
flag[i]=true;
dfs(cnt+1,max(alltime,timee[i].startt)+timee[i].needd);
flag[i]=false;
}
}
}
int main(){
cin>>T;
while(T--){
cin>>n;
key=false;
memset(flag,0,sizeof flag);
for(int i=1;i<=n;i++) cin>>timee[i].startt>>timee[i].lastt>>timee[i].needd;
dfs(0,0);
if(key) cout<<"YES"<<endl;
else cout<<"NO"<<endl;
}
return 0;
}