一直对dfs不太熟包括使用dfs回溯 和dfs深搜找子树 经常卡壳裸题也很难直接写出来 特地写此记录贴 记录下遇到的和dfs相关的题 以及思路和题解
牛牛嚯可乐（牛客小白月赛)
dfs板子题经典的深搜然后回溯 暴力的找到从初始字符到给定字符的最小操作数 最后取min即可 由于方案数是有限种的所以不剪枝的情况下 也不会 发生爆内存的情况
Ac代码：
#include <bits/stdc++.h>
using namespace std;
int ans = 10;
char a[10];
char b[] = "cocacola";
inline void dfs(int pos, int move)//暴力搜索从起始字符到所有字符的最小操作次数
{
if(pos == 8)//当操作到第8个字符的时候
return (void)(ans = min(ans, move));
if(a[pos] == b[pos])
dfs(pos + 1, move);
else
{
for (int i = pos + 1; i <= 7; i++)
if(a[i] == b[pos])
{
swap(a[i], a[pos]);
dfs(pos + 1, move + 1);
swap(a[i], a[pos]);
}
}
}
int main()
{
scanf("%s", a);
dfs(0, 0);//起点位置操作数为0
cout << ans << endl;
return 0;
}
Sequence I
思路:观察到N比较可疑发现方案没有特殊性质直接搜索所有方案取最小的即可
其中每一个位置左合并和右合并是等价的所以只用按一个方向合并即可 否则会直接超时
个人AC代码：
/*
Noe
*/
#include<bits/stdc++.h>
#pragma GCC optimize(2)
#define x first
#define y second
using namespace std;
typedef pair<int,int>PII;
typedef long long LL;
const int M=2010;
const int mod=1e9+7;
const int N=1e6+10;
int dx[4]={0,1,0,-1};
int dy[4]={-1,0,1,0};
typedef long long LL;
int father[N];
int p[N];//素数数组
int gcd(int a,int b)
{
return b?gcd(b,a%b):a;
}
bool is_prime(int x)
{
if(x<2)return false;
for(int i=2;i<=x/i;i++)
if(x%i==0)return false;
return true;
}
int get_prime(int x)
{
int cnt=0;
bool st[N];
memset(st,false,sizeof st);
for(int i=2;i<=x;i++)
{
if(!st[i])p[cnt++]=i;
for(int j=0;j<cnt&&1LL*p[j]*i<=x;j++)
{
st[p[j]*i]=true;
if(i%p[j]==0)break;
}
}
return cnt;
}
int lcm(int a,int b){return a*b/gcd(a,b);};
LL c[M][M];
void init()
{
for(int i=0;i<N;i++)
for(int j=0;j<i;j++)
if(!j)c[i][j]=1;
else c[i][j]=(c[i-1][j-1]+c[i-1][j]);
}
int n;
int ans;//a.size()-1==n;
void dfs(int pos,vector<int>a)
{
a[pos-1]=abs(a[pos]-a[pos-1]);
for(int i=pos;i<=a.size()-2;i++)a[i]=a[i+1];
a.pop_back();
for(int i=2;i<=a.size()-1;i++)dfs(i,a);
if(a.size()==2)return(void)(ans=min(ans,a[1]));
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
// freopen("test.in","r",stdin);
int t;cin>>t;
while(t--)
{
cin>>n;
vector<int>a(n+1);
ans=0x3f3f3f3f;
for(int i=1;i<=n;i++)cin>>a[i];
for(int i=2;i<=n;i++)dfs(i,a);
cout<<ans<<endl;
}
return 0;
}
逆十字代码:
#include<bits/stdc++.h>
using namespace std;
int n,a[10],T;
int dfs(int x)
{
if (x==1) return a[1];
int ans=1000000000;
for (int i=1; i<x; i++)
{
int nw1=a[i],nw2=a[i+1];
a[i]=abs(nw1-nw2);
for (int j=i+1; j<x; j++) a[j]=a[j+1];
ans=min(ans,dfs(x-1));
for (int j=x; j>i+1; j--) a[j]=a[j-1];
a[i+1]=nw2,a[i]=nw1;
}
return ans;
}
int main()
{
scanf("%d",&T);
while (T--)
{
scanf("%d",&n);
for (int i=1; i<=n; i++) scanf("%d",&a[i]);
printf("%d\n",dfs(n));
}
return 0;
}
牛客小白月赛(40)
体操队形
题意:给定一个序列 求给定序列最多有几种拓扑序
- 法1： 由于n很小 10!近似3e6 直接暴力搜索出所有排序 并逐一判断即可
AC代码：
#include<bits/stdc++.h>
#pragma GCC optimize(2)
using namespace std;
typedef pair<int,int>PII;
typedef unsigned long long ull;
typedef long long LL;
const int M=2010;
const int INF=0x3f3f3f3f;
const int mod=1e9+7;
const int N=2e5+10;
int dx[4]={0,1,0,-1};
int dy[4]={-1,0,1,0};
int a[100];
int p[100];
int n;
bool solve(int p[])
{
int mp[100];
for(int i=1;i<=n;i++)mp[p[i]]=i;//p[i]当前在排列在的位置是i
for(int i=1;i<=n;i++)
if(mp[p[i]]>mp[a[p[i]]])return false; //矛盾了
return true; //无矛盾
}
int fact[100];
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
// freopen("test.in","r",stdin);
cin>>n;
for(int i=1;i<=n;i++)cin>>a[i];
for(int i=1;i<=10;i++)fact[i]=1;
for(int i=2;i<=10;i++)fact[i]=fact[i-1]*i;
for(int i=1;i<=n;i++)p[i]=i;//初始排序 1 2 3 4 5 6 7 8 9 10 */
int ans=0;
for(int i=1;i<=fact[n];i++)
{
if(solve(p))ans++;
next_permutation(p+1,p+1+n);//a的下一个排列
}
cout<<ans<<endl;
return 0;
}
时间复杂度$O(n!n)$
法2：dfs搜索 前面的点先排后面的点后排
AC代码：
#include<bits/stdc++.h>
using namespace std;
int n,a[15],vis[15],ans,in[15];
void dfs(int x)
{
if(x==n)
{
ans++;
return;
}
for(int i=1;i<=n;i++)
if(!vis[i]&&!in[i]){
vis[i]=1;
if(a[i]!=i)in[a[i]]--;
dfs(x+1);
vis[i]=0;
if(a[i]!=i)in[a[i]]++;
}
}
int main()
{
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>a[i];
if(a[i]!=i)in[a[i]]++;
}
dfs(1);
cout<<ans<<endl;
return 0;
}
时间复杂度$O(n!n)$
