常用减枝顺序：

1. 优化搜索顺序：大部分情况下，我们应该优先搜索分支较少的结点
2. 排除等效冗余
3. 可行性剪枝
4. 最优性剪枝
5. 最优化搜索（DP）

165. 小猫爬山

翰翰和达达饲养了 $N$ 只小猫，这天，小猫们要去爬山。

经历了千辛万苦，小猫们终于爬上了山顶，但是疲倦的它们再也不想徒步走下山了（呜咕>_<）。

翰翰和达达只好花钱让它们坐索道下山。

索道上的缆车最大承重量为 $W$，而 $N$ 只小猫的重量分别是 $C_1、C_2\dots \dots C_N$。

当然，每辆缆车上的小猫的重量之和不能超过 $W$。

每租用一辆缆车，翰翰和达达就要付 $1$ 美元，所以他们想知道，最少需要付多少美元才能把这 $N$ 只小猫都运送下山？

输入格式

第 $1$ 行：包含两个用空格隔开的整数，$N$ 和 $W$。

第 $\mathrm{2..}N+1$ 行：每行一个整数，其中第 $i+1$ 行的整数表示第 $i$ 只小猫的重量 $C_i$。

输出格式

输出一个整数，表示最少需要多少美元，也就是最少需要多少辆缆车。

数据范围

$1\le N\le 18$,
$1\le C_i\le W\le 10^8$

输入样例：

5 1996
1
2
1994
12
29

输出样例：

2

思路：

• 在搜索的时候，遍历每只猫，把每只猫放在一辆已经租用的缆车上面，或者是重新租一辆缆车
• 优化搜索顺序：应该首先遍历重量较大的猫，重量大的猫相对于重量较小的猫所产生的分支数量更少
• 可行性剪枝：如果当一辆缆车加上一只猫的重量超过缆车的总和后，则直接剪枝
• 最优化剪枝：如果当前的缆车数量大于当前所记录的结果答案，则直接返回

#include<iostream>
#include<algorithm>
using namespace std;
const int N = 20;
int n, m, w[N], sum[N], ans = N;void dfs(int u, int k){// 最优化剪纸if(k > ans) return;if(u == n){ans = k;return;}for (int i = 0; i < k; i++){if(sum[i] + w[u] <= m){ // 可行性剪枝sum[i] += w[u];dfs(u + 1, k);sum[i] -= w[u]; // 恢复现场}}sum[k] = w[u];dfs(u + 1, k + 1);sum[k] = 0; // 恢复现场
}int main(){cin >> n >> m;for (int i = 0; i < n; i++) cin >> w[i];sort(w, w + n);reverse(w, w + n); // 从大到小dfs(0, 0);cout << ans << endl;return 0;
}

166. 数独

数独 是一种传统益智游戏，你需要把一个 $9\times 9$ 的数独补充完整，使得数独中每行、每列、每个 $3\times 3$ 的九宫格内数字 $1\sim 9$ 均恰好出现一次。

请编写一个程序填写数独。

输入格式

输入包含多组测试用例。

每个测试用例占一行，包含 $81$ 个字符，代表数独的 $81$ 个格内数据（顺序总体由上到下，同行由左到右）。

每个字符都是一个数字（$1-9$）或一个 .（表示尚未填充）。

您可以假设输入中的每个谜题都只有一个解决方案。

文件结尾处为包含单词 end 的单行，表示输入结束。

输出格式

每个测试用例，输出一行数据，代表填充完全后的数独。

输入样例：

4.....8.5.3..........7......2.....6.....8.4......1.......6.3.7.5..2.....1.4......
......52..8.4......3...9...5.1...6..2..7........3.....6...1..........7.4.......3.
end

输出样例：

417369825632158947958724316825437169791586432346912758289643571573291684164875293
416837529982465371735129468571298643293746185864351297647913852359682714128574936

思路：tpl

• 暴力搜索，但是直接暴力搜索会超时，因此需要进行剪枝
• 优化搜索顺序：很明显，我们肯定是从当前能填合法数字最少的位置开始填数字
• 排除等效冗余：任意一个状态下，我们只需要找一个位置填数即可，而不是找所有的位置和可填的数字
• 位运算：很明显这里面check判定很多，我们必须优化这个check，所以我们可以对于，每一行，每一列，每一个九宫格，都利用一个九位二进制数保存，当前还有哪些数字可以填写
• lowbit：我们这道题目当前得需要用 lowbit运算取出当前可以能填的数字

#include <cstring>
#include <iostream>
#include <algorithm>using namespace std;const int N = 9, M = 1 << N;int ones[M], map[M];
int row[N], col[N], cell[3][3];
char str[100];void init()
{for (int i = 0; i < N; i ++ )row[i] = col[i] = (1 << N) - 1;for (int i = 0; i < 3; i ++ )for (int j = 0; j < 3; j ++ )cell[i][j] = (1 << N) - 1;
}void draw(int x, int y, int t, bool is_set)
{if (is_set) str[x * N + y] = '1' + t;else str[x * N + y] = '.';int v = 1 << t;if (!is_set) v = -v;row[x] -= v;col[y] -= v;cell[x / 3][y / 3] -= v;
}int lowbit(int x)
{return x & -x;
}int get(int x, int y)
{return row[x] & col[y] & cell[x / 3][y / 3];
}bool dfs(int cnt)
{if (!cnt) return true;int minv = 10;int x, y;for (int i = 0; i < N; i ++ )for (int j = 0; j < N; j ++ )if (str[i * N + j] == '.'){int state = get(i, j);if (ones[state] < minv){minv = ones[state];x = i, y = j;}}int state = get(x, y);for (int i = state; i; i -= lowbit(i)){int t = map[lowbit(i)];draw(x, y, t, true);if (dfs(cnt - 1)) return true;draw(x, y, t, false);}return false;
}int main()
{for (int i = 0; i < N; i ++ ) map[1 << i] = i;for (int i = 0; i < 1 << N; i ++ )for (int j = 0; j < N; j ++ )ones[i] += i >> j & 1;while (cin >> str, str[0] != 'e'){init();int cnt = 0;for (int i = 0, k = 0; i < N; i ++ )for (int j = 0; j < N; j ++, k ++ )if (str[k] != '.'){int t = str[k] - '1';draw(i, j, t, true);}else cnt ++ ;dfs(cnt);puts(str);}return 0;
}

167. 木棒

乔治拿来一组等长的木棒，将它们随机地砍断，使得每一节木棍的长度都不超过 $50$ 个长度单位。

然后他又想把这些木棍恢复到为裁截前的状态，但忘记了初始时有多少木棒以及木棒的初始长度。

请你设计一个程序，帮助乔治计算木棒的可能最小长度。

每一节木棍的长度都用大于零的整数表示。

输入格式

输入包含多组数据，每组数据包括两行。

第一行是一个不超过 $64$ 的整数，表示砍断之后共有多少节木棍。

第二行是截断以后，所得到的各节木棍的长度。

在最后一组数据之后，是一个零。

输出格式

为每组数据，分别输出原始木棒的可能最小长度，每组数据占一行。

数据范围

数据保证每一节木棍的长度均不大于 $50$。

输入样例：

9
5 2 1 5 2 1 5 2 1
4
1 2 3 4
0

输出样例：

6
5

思路：

• 

• 

• 

• 

#include<iostream>
#include<cstring>
#include<algorithm>using namespace std;const int N=70;int w[N],sum,length,n;
bool st[N];bool dfs(int u,int part,int start)//第u组,part第u组的已有长度,start表示第u组的枚举位置;
{if(u*length==sum) return true;//如果总长度到达了,返回trueif(part==length) return dfs(u+1,0,0);//true要一直持续不断的返回,false同理for(int i=start;i<=n;i++){if(st[i]) continue;if(w[i]+part>length) continue;st[i]=true;//标记已经使用if(dfs(u,w[i]+part,i+1)) return true;//因为前i个棍子都在第u组枚举了,所以直接从第i+1根棍子开始枚举st[i]=false;//返回上层分支时要恢复现场(枚举该组不选择第i根根子的方案)if(!part||w[i]+part==length) return false;//如果第一根失败了或者最后一根失败了,就一定失败int j=i;//如果i失败了,那么长度跟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,length=1;for(int i=1;i<=n;i++){scanf("%d",&w[i]);sum+=w[i];//总和}//倒着排序,以减少分支sort(w+1,w+n+1);reverse(w+1,w+n+1);while(1)//枚举length的长度{if(sum%length==0&&dfs(0,0,0)){printf("%d\n",length);break;}length++;}}
}

168. 生日蛋糕

$7$ 月 $17$ 日是 Mr.W 的生日，ACM-THU 为此要制作一个体积为 $N\pi$ 的 $M$ 层生日蛋糕，每层都是一个圆柱体。

设从下往上数第 $i$ 层蛋糕是半径为 $R_i$，高度为 $H_i$ 的圆柱。

当 $i<M$ 时，要求 $R_i>R_{i+1}$ 且 $H_i>H_{i+1}$。

由于要在蛋糕上抹奶油，为尽可能节约经费，我们希望蛋糕外表面（最下一层的下底面除外）的面积 $Q$ 最小。

令 $Q=S\pi$ ，请编程对给出的 $N$ 和 $M$，找出蛋糕的制作方案（适当的 $R_i$ 和 $H_i$ 的值），使 $S$ 最小。

除 $Q$ 外，以上所有数据皆为正整数。

输入格式

输入包含两行，第一行为整数 $N$，表示待制作的蛋糕的体积为 $N\pi$。

第二行为整数 $M$，表示蛋糕的层数为 $M$。

输出格式

输出仅一行，是一个正整数 $S$（若无解则 $S=0$）。

数据范围

$1\le N\le 10000$,
$1\le M\le 20$

输入样例：

100
2

输出样例：

68

思路：

记最底层为 $m$,很容易观察得出，表面积的公式为$S_{总}=S_{m层上侧面积}$$+{\sum }_{i=1}^{m}2\pi R_i{H}_i$

而体积为$V_{总}={\sum }_{i=1}^m\pi R_i^2{H}_i$

有了两个公式，还有题目给出的每层最小高度和最小半径，就知道可以用剪枝+暴搜来做这个题

1. 优化搜索顺序

   • 层间：从下到上

   • 层内：先枚举半径再枚举高（半径相对于高来说对体积的影响较大，因为半径是平方级别），半径由大到小，高度由大到小

2. 可行性剪枝

   记总体积为 $n$，当前层位 $u$, 第 $u$ 层的高度为 $H_u$, 半径为 $R_u$， 体积为 $V_u$，第 $m$ 层到第 $u$ 层体积的累计值 $V$

   1. 对于 $R$，当前为第 $u$ 层，第 $u$ 层的体积为 $V_u$。$R$ 最小的取值应该是当前的层号 $u$ ，$R$ 的最大值应该由两部分决定
   • $u+1$ 层的半径减 $1$, 记 $R_{u+1}-1$
   • 第 $u$ 层体积的最大值除第 $u$ 层高度的最小值 $u$

   这两者的最小值，故有以下等式成立$u\le R_u\le \min (R_{u+1}-1,\sqrt{\frac{n-min{\sum }_{i=1}^{u-1}{V}_i-V}{u}})$

   1. 对于第 $u$ 层高度 $h$ 的推导同理，高度 $h$ 的取值的最小值应该大于等于层号 $u$，高度的最小值由两部分决定
   • $H_{u+1}-1$
   • 第 $u$ 层体积的最大值除第 $u$ 层的底面积最小值

   故同理可得出下列等式 $u\le Hu\le \min (H_{u+1}-1,\frac{n-min{\sum }_{i=1}^{u-1}{V}_i-V}{R_u^2})$

   1. 考虑体积的剪枝：预处理前 $u$ 层的体积最小值 $min{\sum }_{i=1}^{u-1}{V}_i$，会有 $V+min{\sum }_{i=1}^{u-1}{V}_i\le n$

   2. 推表面积公式和体积公式的关系

      第一层到第 $u$ 层的表面积有（不考虑 $\pi$）：$S_{1-u}=2{\sum }_{i=1}^u{R}_i{H}_i=\frac{2}{R_{u+1}}{\sum }_{i=1}^u{R}_{u+1}{R}_i{H}_i>\frac{2}{R_{u+1}}{\sum }_{i=1}u{R}_i^2{H}_i$

      第一层到第 u 层的体积有：$n-V={\sum }_{i=1}^u{R}_i^2{H}_i$

      所以惊奇地发现：$S_{1-u}>\frac{2(n-V)}{R_{u+1}}$

      因此 $S_{总}=S+S_{1-u}>=S_{ans}$，即 $S+\frac{2(n-V)}{R_{u+1}}>=S_{ans}$ 时就可以剪枝掉（最优性剪枝)

3. 最优性剪枝

   记第 $m$ 层到第 $u$ 层表面积的累计值 $S$，第 $1$ 到第 $u-1$ 层表面积的最小值为 $min{\sum }_{i=1}^{u-1}{S}_i$则

   应该有 $S+min{\sum }_{i=1}^{u-1}{S}_i<res$

#include<iostream>
#include<cmath>
using namespace std;const int N = 24, INF = 1e9;int n, m;
int minv[N], mins[N];
int res = INF;//记录每层的半径和高，因为会用到上一层的高度
int R[N], H[N];//u当前层次，v当前处理的体积和，s当前处理的面积和
void dfs(int u, int v, int s)
{if(v + minv[u] > n) return;if(s + mins[u] >= res) return;if (s + 2 * (n - v) / R[u + 1] >= res) return;if(!u){if(v == n) res = s;return;}//搜索顺序，先R后H，从大到小for(int r = min(R[u + 1] - 1,(int)sqrt((n - v - minv[u - 1]) / u)); r >= u; r--)for(int h = min(H[u + 1] - 1, (n - v - minv[u - 1]) / r / r); h >= u; h--){H[u] = h, R[u] = r;//最底层的时候需要加上r*rint t = u == m ? r * r : 0;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;}//m+1层不存在，作为哨兵，减少边界情况的判断R[m + 1] = H[m + 1] = INF;dfs(m, 0, 0);if(res == INF) res = 0;cout << res << endl;return 0;
}

详细见博客内容：http://47.108.226.193/index.php/archives/141/