Part1.3 基础算法-深搜的剪枝技巧

A 数的划分

这个题还是要好好看一下的，用自己的想法和思路。

#include <cstdio>using namespace std;const int N = 10010;int n, k;
int a[N];
int ans;void dfs(int u, int val)
{
    if (val <= 0) return;if (u >= k){
    ans ++;return;}for (int i = a[u - 1]; i <= val / (k - u + 1); i ++ ){
    a[u] = i;val -= i;dfs(u + 1, val);val += i;}
}int main()
{
    scanf("%d%d", &n, &k);a[0] = 1;dfs(1, n);printf("%d\n", ans);return 0;
}

B 生日蛋糕

#include <cstdio>
#include <cmath>
#include <algorithm>using namespace std;const int N = 10010;int n, m;
int r[N], h[N];
int minv[N], mins[N];
int ans = 1 << 30;void dfs(int u, int v, int s)
{
    // printf("%d ^ %d ^ %d\n", u, v, s);//剪枝//当前体积为m~u+1的体积，加上最小的预估1~u的体积if (v + minv[u] > n) return;//如果最小也等于ans的话，也不用尝试了，已经有比他更优的方案了。if (s + mins[u] >= ans) return;if (s + 2 * (n - v) / r[u + 1] >= ans) return;if (u < 0) return;if (u == 0){
    if (v == n) ans = min(ans, s);return;}//往下搜索，循环r和h//从大到小的循环顺序for (int i = min(r[u + 1] - 1, (int)(sqrt(n - v))); i >= u; i -- )for (int j = min(h[u + 1] - 1, (n - v) / i / i); j >= u; j -- ){
    // if (u == m) s += i * i;// r[u] = i, h[u] = j;// dfs(u - 1, v + i * i * j, s + 2 * i * j);int t = 0;if (u == m) t = i * i;r[u] = i, h[u] = j;dfs(u - 1, v + i * i * j, s + 2 * i * j + t);}
}int main()
{
    scanf("%d%d", &n, &m);//预估函数for (int i = 1; i <= m; i ++ ) minv[i] = minv[i - 1] + i * i * i;for (int i = 1; i <= m; i ++ ) mins[i] = mins[i - 1] + i * i * 2;//给当u为m使用的r[m + 1] = h[m + 1] = 1 << 30;//需要传参，当前层数，当前体积，当前面积dfs(m, 0, 0);if (ans == 1 << 30) ans = 0;printf("%d\n", ans);return 0;
}

C 小木棍

#include <cstdio>
#include <algorithm>using namespace std;const int N = 110;int n;
int a[N];
int sum;
bool st[N];//已经拼好has-1个，正在拼当前的第has个小木棍，长度为len，个数为cnt个，现在正在拼的长度为lens，当前行上一个拼的木棍的下标
bool dfs(int has, int len, int cnt, int lens, int last)
{
    if (has > cnt) return true;//已经拼好了//当前的小木棍已经拼好了，可以开始拼下一个小木棍了if (lens == len){
    if (dfs(has + 1, len, cnt, 0, 1)) return true;}//现在搞得是当前层，和下一层没有关系//枚举当前层，进行木棍的拼凑int fail = 0;for (int i = last; i <= n; i ++ )if (!st[i]){
    if (lens + a[i] > len) continue;if (fail == a[i]) continue;// if (lens + a[i] > len) return false;// if (fail == a[i]) return false;st[i] = true;if (dfs(has, len, cnt, lens + a[i], i + 1)) return true;fail = a[i];st[i] = false;//如果现在已经拼好了，或者要进入下一层了，都不需要继续搜索了// printf("%d %d %d\n", lens, a[i], lens + a[i]);if (lens == 0) return false;}return false;
}
int main()
{
    scanf("%d", &n);for (int i = 1; i <= n; i ++ ){
    scanf("%d", &a[i]);sum += a[i];}sort(a + 1, a + 1 + n);reverse(a + 1, a + 1 + n);// printf("%d %d %d\n", a[n], sum, n);for (int len = a[n]; len <= sum; len ++ )if (sum % len == 0){
    // printf("%d %d\n", len, sum / len);for (int i = 0; i <= n; i ++ ) st[i] = false;if (dfs(1, len, sum / len, 0, 1)){
    printf("%d\n", len);return 0;}}
}

D　Addition Chains

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>using namespace std;const int N = 110;int n;
int a[N];
int depth;
bool st[N];bool dfs(int u)
{
    // cout << u << "\n";if (u > depth) return false;if (u == depth && a[u - 1] == n) return true;memset(st, 0, sizeof st);for (int i = u - 1; i >= 0; i -- )for (int j = i; j >= 0; j -- ){
    int t = a[i] + a[j];if (t > n) continue;//剪枝if (t <= a[u - 1]) continue;//剪枝if (t > 2 * a[u - 1]) continue;//如果出现这情况，说明我们之前可以将这些枚举到了，当然，可能和st数组重复了if (st[t]) continue;st[t] = true;a[u] = t;if (dfs(u + 1)) return true;}return false;
}
int main()
{
    while (cin >> n){
    if (!n) return 0;a[0] = 1;for (depth = 0; !dfs(1); depth ++ );for (int i = 0; i < depth; i ++ )printf("%d ", a[i]);puts("");}
}

E weight

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>using namespace std;const int N = 2010, M = 510;int n, m;
int a[N], b[M];
int path[N];void dfs(int u, int L, int R, int s, int t)
{
    if (u > 2 * n + 1) return;if (L == R){
    if (a[2 * n] - s - t <= 500 && b[a[2 * n] - s - t]){
    path[L] = a[2 * n] - s - t;for (int i = 1; i <= n; i ++ )printf("%d ", path[i]);puts("");exit(0);}return;}if (a[u] - s <= 500 && b[a[u] - s]){
    path[L] = a[u] - s;dfs(u + 1, L + 1, R, a[u], t);}if (a[u] - t <= 500 && b[a[u] - t]){
    path[R] = a[u] - t;dfs(u + 1, L, R - 1, s, a[u]);}
}int main()
{
    cin >> n;for (int i = 1; i <= n << 1; i ++ ) cin >> a[i];cin >> m;for (int i = 1; i <= m; i ++ ) {
    int x; cin >> x; b[x] ++;}sort(a + 1, a + 1 + 2 * n);dfs(1, 1, n, 0, 0);return 0;
}

F 埃及分数

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>using namespace std;typedef long long ll;const int N = 1010, M = 1e7;ll n, m, depth;
int path[N], ans[N];ll gcd(ll a, ll b)
{
    return b ? gcd(b, a % b) : a;
}bool dfs(int u, ll a, ll b)
{
    if (u == depth - 1){
    ll d = gcd(a, b);a /= d;b /= d;// if (b % a) return false;if (a == 1){
    path[u] = b;if (path[u - 1] >= path[u]) return false;if (!ans[u] || ans[u] > path[u])for (int i = 0; i < depth; i ++ )ans[i] = path[i];return true;}return false;}//1/i < a/b 也就是 i > b / a，即i的下界为b/a+1//因为a/b - 1/i(depth - u) <= 0，这是i的上界bool flag = false;for (int i = max((int)(b / a) + 1, path[u - 1] + 1); a * i - b * (depth - u) <= 0; i ++ ){
    ll x = a * i - b;ll y = b * i;ll d = gcd(x, y);x /= d;y /= d;if (x < 0 || y < 0) continue;path[u] = i;if (dfs(u + 1, x, y)) flag = 1;}return flag;
}
int main()
{
    cin >> n >> m;ll d = gcd(n, m);n /= d;m /= d;if (n == 1){
    cout << m << endl;}else{
    for (depth = 2; !dfs(0, n, m); depth ++ );for (int i = 0; i < depth; i ++ )printf("%d ", ans[i]);return 0;}
}

G 平板涂色

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>using namespace std;const int N = 14;struct Node
{
    int y1, x1, y2, x2, c;
}a[N];int n;
vector<int> v[N];
int ans = 1e9;
bool st[N];
//判断当前矩形是否可以染色，如果上面没有矩形或者上面的矩形都已经染好色了，就返回true
bool check(int u)
{
    if (v[u].empty()) return true;for (int i = 0; i < v[u].size(); i ++ )if (!st[v[u][i]]) return false;return true;
}//cnt：已经染了多少个，res：使用了多少中颜色，c：上一个颜色是哪一种颜色
void dfs(int cnt, int res, int c)
{
    if (res >= ans) return;if (cnt == n){
    ans = res;return;}for (int i = 0; i < n; i ++ ){
    if (st[i]) continue;if (check(i)){
    st[i] = true;dfs(cnt + 1, res + (c != a[i].c), a[i].c);st[i] = false;}}
}
int main()
{
    cin >> n;for (int i = 0; i < n; i ++ ){
    int x1, y1, x2, y2, c;cin >> y1 >> x1 >> y2 >> x2 >> c;a[i] = {
    y1, x1, y2, x2, c};}//将当前矩形的正上方的矩形记录下来for (int i = 0; i < n; i ++ )for (int j = 0; j < n; j ++ )if (i != j && a[i].y1 == a[j].y2 && a[j].x1 <= a[i].x2 && a[j].x2 >= a[i].x1){
    v[i].push_back(j);}dfs(0, 0, -1);cout << ans << endl;// for (int i = 0; i < n; i ++ )// {
    // printf("%d : ", i);// for (auto it : v[i])// cout << it << " ";// cout << endl;// }return 0;
}