[Acwing面向模型编程]dfs
题目1：AcWing 1118. 分成互质组
分析：
枚举每个数，他既可以放到当前已经有的箱子里，也可以新开一个箱子。
代码：
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;//三年竞赛一场空，不开long long见祖宗
//typedef __int128 lll;
#define print(i) cout << "debug: " << i << endsl
#define close() ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#define mem(a, b) memset(a, b, sizeof(a))
#define pb(a) push_back(a)
#define x first
#define y second
typedef pair<int, int> pii;
const ll mod = 1e9 + 7;
const int maxn = 1e5 + 10;
const int inf = 0x3f3f3f3f;
int n;
int a[20];
int group[20][20], cnt[20];
int ans = 10;
bool judge(int now, int val)
{
for(int i = 1; i <= cnt[now]; i++)
if(__gcd(group[now][i], val) > 1)
return false;
return true;
}
void dfs(int id, int num)
{
if(num >= ans) return;
if(id == n + 1)
{
ans = min(ans, num);
return;
}
for(int i = 1; i <= num; i++)
{
if(judge(i, a[id]))
{
group[i][++cnt[i]] = a[id];
dfs(id + 1, num);
cnt[i]--;
}
}
cnt[num + 1] = 1;
group[num + 1][cnt[num + 1]] = a[id];
dfs(id + 1, num + 1);
cnt[num + 1] = 0;
}
int main()
{
cin >> n;
for(int i = 1; i <= n; i++) cin >> a[i];
dfs(1, 0);
cout << ans << endl;
}
题目2：165. 小猫爬山
分析：做法跟上题一样
代码：
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;//三年竞赛一场空，不开long long见祖宗
//typedef __int128 lll;
#define print(i) cout << "debug: " << i << endsl
#define close() ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#define mem(a, b) memset(a, b, sizeof(a))
#define pb(a) push_back(a)
#define x first
#define y second
typedef pair<int, int> pii;
const ll mod = 1e9 + 7;
const int maxn = 1e5 + 10;
const int inf = 0x3f3f3f3f;
int n, m;
int a[20];
int group[20];
int ans = 20;
void dfs(int id, int num)
{
if(num >= ans) return;
if(id == n + 1)
{
ans = min(ans, num);
return;
}
for(int i = 1; i <= num; i++)
{
if(group[i] + a[id] <= m)
{
group[i] += a[id];
dfs(id + 1, num);
group[i] -= a[id];
}
}
group[num + 1] = a[id];
dfs(id + 1, num + 1);
group[num + 1] = 0;
}
int main()
{
cin >> n >> m;
for(int i = 1; i <= n; i++) cin >> a[i];
dfs(1, 0);
cout << ans << endl;
}
题目3：AcWing 166. 数独
分析：
这个题写起来比较麻烦，这里只说一下思想吧，实现见代码
我们搜索的顺序是：先搜可选数目最小的格子
我们用二进制存储每行每列每个3*3的状态。
代码：
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;//三年竞赛一场空，不开long long见祖宗
//typedef __int128 lll;
#define print(i) cout << "debug: " << i << endsl
#define close() ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#define mem(a, b) memset(a, b, sizeof(a))
#define pb(a) push_back(a)
#define x first
#define y second
typedef pair<int, int> pii;
const ll mod = 1e9 + 7;
const int maxn = 1e5 + 10;
const int inf = 0x3f3f3f3f;
const int N = 9;
char s[maxn];
int col[N], rol[N];
int cube[3][3];
int ones[1 << N], ma[1 << N];
int lowbit(int x)
{
return x & -x;
}
void make()
{
for(int i = 0; i < N; i++) ma[1 << i] = i;
for(int i = 0; i < 1 << N; i++)
{
int state = i;
while(state)
ones[i]++, state -= lowbit(state);
}
}
int get(int x, int y)
{
return rol[x] & col[y] & cube[x / 3][y / 3];
}
void init()
{
for(int i = 0; i < N; i++) col[i] = rol[i] = (1 << N) - 1;
for(int i = 0; i < 3; i++)
for(int j = 0; j < 3; j++)
cube[i][j] = (1 << N) - 1;
}
void draw(int x, int y, int t, int add)
{
if(add) s[x * N + y] = t + '1';
else s[x * N + y] = '.';
int val = 1 << t;
if(!add) val = -val;
rol[x] -= val, col[y] -= val;
cube[x / 3][y / 3] -= val;
}
bool dfs(int cnt)
{
if(!cnt) return true;
int minn = 10, mini, minj;
for(int i = 0; i < N; i++)
for(int j = 0; j < N; j++)
{
if(s[i * N + j] == '.')
{
int state = get(i, j);
if(ones[state] < minn)
minn = ones[state], mini = i, minj = j;
}
}
int state = get(mini, minj);
for(int i = state; i; i -= lowbit(i))
{
int t = ma[lowbit(i)];
draw(mini, minj, t, true);
if(dfs(cnt - 1)) return true;
draw(mini, minj, t, false);
}
return false;
}
int main()
{
make();
while(cin >> s && s[0] != 'e')
{
int cnt = 0;
init();
for(int i = 0, k = 0; i < N; i++)
for(int j = 0; j < N; j++, k++)
{
if(s[k] != '.')
draw(i, j, s[k] - '1', true);
else cnt++;
}
dfs(cnt);
cout << s << endl;
}
}
题目4：167. 木棒
分析：
3个剪枝：
- 长度递增枚举
- 跳过长度相等的木棒
- 本轮第一个或者最后一个木棒失败了，则本次枚举一定失败。
代码：
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;//三年竞赛一场空，不开long long见祖宗
//typedef __int128 lll;
#define print(i) cout << "debug: " << i << endsl
#define close() ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#define mem(a, b) memset(a, b, sizeof(a))
#define pb(a) push_back(a)
#define x first
#define y second
typedef pair<int, int> pii;
const ll mod = 1e9 + 7;
const int maxn = 1e5 + 10;
const int inf = 0x3f3f3f3f;
int n;
int a[maxn], vis[maxn];
int sum;
int len;
bool dfs(int nownum, int nowlen, int pos)
{
if(nownum * len == sum) return true;
if(nowlen == len) return dfs(nownum + 1, 0, 1);
for(int i = pos; i <= n; i++)
{
if(vis[i] || nowlen + a[i] > len) continue;
vis[i] = 1;
if(dfs(nownum, nowlen + a[i], pos + 1)) return true;
vis[i] = 0;
if(nowlen == 0 || nowlen + a[i] == len) return false;
int j = i;
while(j <= n && a[j] == a[i]) j++;
i = j - 1;
}
return false;
}
int main()
{
while(cin >> n && n)
{
sum = 0;
mem(vis, 0);
for(int i = 1; i <= n; i++) cin >> a[i], sum += a[i];
sort(a + 1, a + 1 + n, [&](int a, int b){
return a > b;
});
for(len = 1; ; len++)
if(sum % len == 0 && dfs(0, 0, 1))
{
cout << len << endl;
break;
}
}
}
题目5：168. 生日蛋糕
分析：
具体分析见acwing算法提高课…
代码：
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;//三年竞赛一场空，不开long long见祖宗
//typedef __int128 lll;
#define print(i) cout << "debug: " << i << endsl
#define close() ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#define mem(a, b) memset(a, b, sizeof(a))
#define pb(a) push_back(a)
#define x first
#define y second
typedef pair<int, int> pii;
const ll mod = 1e9 + 7;
const int maxn = 1e5 + 10;
const int inf = 0x3f3f3f3f;
int n, m;
int minv[maxn], mins[maxn];
int nowr[maxn], nowh[maxn];
int ans = inf;
void dfs(int nowlayer, int nowv, int nows)
{
if(nowv + minv[nowlayer] > n) return; //可行性剪枝
if(nows + mins[nowlayer] >= ans) return; //最优化剪枝
if(nows + 2 * (n - nowv) / nowr[nowlayer + 1] >= ans) return; //最优化剪枝（关键）
if(nowlayer == 0)
{
if(nowv == n) ans = nows;
return;
}
for(int r = min(nowr[nowlayer + 1] - 1, (int)sqrt(n - nowv)); r >= nowlayer; r--)
for(int h = min(nowh[nowlayer + 1] - 1, (n - nowv) / r / r); h >= nowlayer; h--)
{
nowr[nowlayer] = r, nowh[nowlayer] = h;
int add = 0;
if(nowlayer == m) add = r * r;
dfs(nowlayer - 1, nowv + r * r * h, nows + 2 * r * h + add);
}
}
int main()
{
cin >> n >> m;
for(int i = 1; i <= m; i++)
minv[i] = minv[i - 1] + i * i * i, mins[i] = mins[i - 1] + 2 * i * i;
nowr[m + 1] = nowh[m + 1] = inf;
dfs(m, 0, 0);
if(ans == inf) ans = 0;
cout << ans << endl;
}