AcWing 167. 木棒
本题链接：AcWing 167. 木棒
本博客提供本题截图：
本题解析
所有木棍的长度之和为sum, 我们的木棒长度为length，注意我们只有sum % length == 0的时候才会进行dfs这个操作
优化搜索顺序：按照木棍的质量从大到小去枚举木棍
排除等效冗余：
1.按照组合数的方式进行枚举
2.如果当前木棍加入到当前木棒中失败了，则跳过所有长度和当前木棍相等的木棍
3.如果加入木棒的第一根木棍就失败了，则一定失败
4.如果加入木棒的最后一根木棍失败了，则一定失败
我们的dfs中传入三个参数：第u组，第u组的长度，第u组开始枚举的位置
AC代码
#include <cstring> #include <iostream> #include <algorithm> using namespace std; const int N = 70; int n; int w[N]; int sum, length; bool st[N]; bool dfs(int u, int cur, int start) { if (u * length == sum) return true; if (cur == length) return dfs(u + 1, 0, 0); for (int i = start; i < n; i ++ ) { if (st[i] || cur + w[i] > length) continue; st[i] = true; if (dfs(u, cur + w[i], i + 1)) return true; st[i] = false; if (!cur || cur + w[i] == length) return false; int j = i; while (j < n && w[j] == w[i]) j ++ ; i = j - 1; } return false; } int main() { while (cin >> n, n) { memset(st, 0, sizeof st); sum = 0; for (int i = 0; i < n; i ++ ) { cin >> w[i]; sum += w[i]; } sort(w, w + n); reverse(w, w + n); length = 1; while (true) { if (sum % length == 0 && dfs(0, 0, 0)) { cout << length << endl; break; } length ++ ; } } return 0; }
AcWing 168. 生日蛋糕
本题链接：AcWing 168. 生日蛋糕
本博客提供本题截图：
本题解析
玄学剪枝题（逃
本题时间卡的特别死，且推导过程难得离谱
来说下剪枝：
1.先枚举半径再枚举高度，原因：因为在计算体积的时候半径是二次方，对结果的影响较大
2.第u层到最高层的最小面积和体积时固定的，即我们的minv数组函数和mins数组
3.第u层的半径满足：u ≤ R(u) ≤ min{R(u + 1) - 1, sqrt(n - v)} （n是总体积，v是当前的体积）
第u层的高度满足：u ≤ H(u) ≤ min{H(u + 1) - 1，(n - v) / r * r}
推导：我们知道体积公式：V = r * r * h，所以当我们的h取1的时候，有V ≥ r * r，即n - v ≥ r * r，的r满足：r ≤ sqrt(n - v)，高度的推导类似于次，但是因为已经确定r了，所以不能把r取任何值
4.玄学剪枝：利用表面积和体积之间的关系进行剪枝（离谱，玄幻）
当我们的当前面积S + 未来表面积S1~u如果≥ ans的话我们就不需要这个分支了
AC代码
#include <cstring> #include <iostream> #include <algorithm> #include <cmath> using namespace std; const int N = 25, INF = 1e9; int n, m; int minv[N], mins[N]; int R[N], H[N]; int ans = INF; void dfs(int u, int v, int s) { if (v + minv[u] > n) return; if (s + mins[u] >= ans) return; if (s + 2 * (n - v) / R[u + 1] >= ans) return; if (!u) { if (v == n) ans = s; return; } for (int r = min(R[u + 1] - 1, (int)sqrt(n - v)); r >= u; r -- ) for (int h = min(H[u + 1] - 1, (n - v) / r / r); h >= u; h -- ) { int t = 0; if (u == m) t = r * r; R[u] = r, H[u] = h; dfs(u - 1, v + r * r * h, s + 2 * r * h + t); } } 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; } R[m + 1] = H[m + 1] = INF; dfs(m, 0, 0); if (ans == INF) ans = 0; cout << ans << endl; return 0; }
三、时间复杂度
dfs时间复杂度为指数级别
