深度优先搜索的剪枝优化还是很灵活的。但常规来说，比较通用的优化思路主要有两类。
- 可行性剪枝
- 最优性剪枝
需要结合题目性质进行一定的理解与探究。必要时还可以加入一些启发式的优化。
一本通上的几个例题和练习做得有点卡，代码也很丑陋。
#10018. 「一本通 1.3 例 1」数的划分
没怎么动脑子就直接dp了
#include <bits/stdc++.h> using namespace std; int n,k; int f[205][9][205]; //?分成?个数 最大不超过? int main() { cin>>n>>k; memset(f,0,sizeof f); f[0][0][1]=1; for(int i=1;i<=n;i++) for(int j=1;j<=k;j++) for(int l=1;l<=i;l++) for(int t=1;t<=l;t++) f[i][j][l]+=f[i-l][j-1][t]; int ans = 0; for(int i=1;i<=n;i++) ans += f[n][k][i]; cout<<ans<<endl; }
#10019. 「一本通 1.3 例 2」生日蛋糕
加入最优性剪枝后，搜索时的枚举顺序就会对时间效率产生影响
// R[i]>R[i+1], H[i]>H[i-1] // Sigma(R^2*H) = V // Sigma(2RH) + Rm^2 = S #include <bits/stdc++.h> using namespace std; const int inf = 0x3f3f3f3f; int n, m, ans = inf; void dfs(int vol, int sur, int dep, int pr, int ph) { if (vol < 0 || sur > ans) return; if (2 * vol / pr + sur > ans) return; if (dep == m + 1) { if (vol == 0) ans = sur; return; } for (int i = pr - 1; i > m - dep; --i) for (int j = ph - 1; j > m - dep; --j) { if (dep == 1) sur = i * i; dfs(vol - i * i * j, sur + 2 * i * j, dep + 1, i, j); } } int main() { cin >> n >> m; dfs(n, 0, 1, sqrt(n), n); if (ans == inf) cout << "0" << endl; else cout << ans << endl; return 0; }
#10020. 「一本通 1.3 例 3」小木棍
听说有个数据点有问题？
#include <bits/stdc++.h> using namespace std; int n, a[105], u[105]; bool dfs(int idx, int rem) { if (rem < 0) return false; if (rem == 0) return true; for (int i = idx; i >= 1; --i) { if (u[i]) continue; u[i] = 1; if (dfs(i - 1, rem - a[i])) return true; u[i] = 0; } return false; } int main() { cin >> n; for (int i = 1; i <= n; i++) cin >> a[i]; sort(a + 1, a + n + 1); int sum = 0; for (int i = 1; i <= n; i++) sum += a[i]; for (int i = a[1]; i <= sum; i++) { if (sum % i) continue; memset(u, 0, sizeof u); int flag = 1; for (int j = 1; j <= sum / i; j++) { if (dfs(n, i) == false) { flag = 0; break; } } if (flag) { cout << i << endl; return 0; } } }
#10021. 「一本通 1.3 例 4」Addition Chains
题目意思描述的不是特别清楚。自己写的时候剪枝边界没选好。
#include <bits/stdc++.h> using namespace std; int n, ans = 105; vector<int> s, a; int u[305]; void dfs(int p) { if (s.size() >= 11) return; if (s.size() >= ans) return; if (p == n + 1) { ans = min(ans, (int)(s.size())); if (ans == (int)(s.size())) a = s; } else for (int i = p; i <= min(2 * p + 1, n); i++) { if (u[i] == 0) continue; for (int j = 0; j < s.size(); j++) u[i + s[j]]++; u[2 * i]++; s.push_back(i); dfs(i + 1); s.pop_back(); for (int j = 0; j < s.size(); j++) u[i + s[j]]--; u[2 * i]--; } } int main() { while (cin >> n) { ans = 105; s.clear(); if (n == 0) return 0; s.push_back(1); u[1] = u[2] = 1; dfs(2); // cout<<ans<<endl; for (int i = 0; i < a.size(); i++) cout << a[i] << " "; cout << endl; } }
#10022. 「一本通 1.3 练习 1」埃及分数
#include <bits/stdc++.h> using namespace std; #define ll long long ll gcd(ll x, ll y) { return y ? gcd(y, x % y) : x; } ll flag = 0; struct frac { ll p, q; frac() { p = q = 1; } frac(ll x) { p = 1; q = x; } frac(ll x, ll y) { p = x; q = y; } void simp() { ll g = gcd(p, q); p /= g; q /= g; } void add(frac &b) { p = p * b.q + q * b.p; q *= b.q; simp(); } void dec(frac &b) { p = p * b.q - q * b.p; q *= b.q; simp(); } } a; ll mx = 0x3f3f3f3f; vector<ll> sta, sans; ll ans, D; void dfs(ll dep, ll lim, frac rem) { // cout<<dep<<" "<<lim<<" "<<rem.p<<"/"<<rem.q<<endl; if (lim >= mx) return; if (dep == 0) { if (rem.p == 0) { flag = 1; mx = min(mx, lim); if (mx == lim) sans = sta; } } else if (dep == 1 && (rem.p == 1 && rem.q > lim)) { flag = 1; mx = min(mx, rem.q); if (mx == rem.q) { sans = sta; sans.push_back(mx); } } else { if (rem.p <= 0 || (rem.p > 0 && rem.q < 0)) return; for (ll i = max(lim, rem.q / rem.p) + 1; i <= 100000; i++) { if ((dep)*rem.q <= rem.p * i) break; sta.push_back(i); frac tmp(i); rem.dec(tmp); dfs(dep - 1, i, rem); rem.add(tmp); sta.pop_back(); } } } int main() { cin >> a.p >> a.q; int g = gcd(a.p, a.q); a.p /= g; a.q /= g; for (ll i = 1; i <= 100; i++) { D = i; dfs(i, 1, a); if (flag) break; } if (flag) { for (ll i = 0; i < sans.size(); i++) cout << sans[i] << " "; cout << endl; } }
#10023. 「一本通 1.3 练习 2」平板涂色
抽象成几个点，有依赖关系的块连边。搜索枚举的时候判断应该在该点之前涂的点是否都涂过了，这样跑的比较快。如果反过来，检验所有应该在该点之后涂的点是否都被涂过，就会跑得比较慢。
#include <bits/stdc++.h> using namespace std; vector<int> g[15]; int a[15][15], n, x[2], y[2], c[15], s[15], u[15], cnt, ans = 0x3f3f3f3f; int _c = 0; void dfs(int pos) { ++_c; if (cnt >= ans) return; if (pos == n + 1) ans = min(ans, cnt); else for (int i = 1; i <= n; i++) { if (u[i]) continue; int fg = 0; for (int j = 0; j < g[i].size(); j++) if (u[g[i][j]] == 0) { fg = 1; break; } if (fg) continue; u[i] = 1; s[pos] = i; if (c[s[pos]] - c[s[pos - 1]]) ++cnt; dfs(pos + 1); if (c[s[pos]] - c[s[pos - 1]]) --cnt; u[i] = 0; s[pos] = 0; } } int main() { cin >> n; for (int i = 1; i <= n; i++) { cin >> x[0] >> y[0] >> x[1] >> y[1] >> c[i]; for (int j = x[0] + 1; j <= x[1]; j++) for (int k = y[0] + 1; k <= y[1]; k++) a[j][k] = i; } for (int i = 1; i <= 9; i++) for (int j = 1; j <= 9; j++) if (a[i][j] && a[i - 1][j] && a[i][j] != a[i - 1][j]) g[a[i][j]].push_back(a[i - 1][j]); for (int i = 1; i <= n; i++) sort(g[i].begin(), g[i].end()), g[i].resize(unique(g[i].begin(), g[i].end()) - g[i].begin()); dfs(1); cout << ans << endl; // cout<<_c<<endl; }
| #10019. 「一本通 1.3 例 2」生日蛋糕 |