第 2 章 枚举与搜索

// 子集枚举（二进制）。用洛谷 P1048 采药的输入格式，演示物品数 m ≤ 20 时的暴力：
// 总时间 T，m 株草药各有采摘时间和价值，每株最多采一次，求总时间不超过 T 时的最大总价值。
// 0 到 2^m - 1 的每个整数恰好对应一个子集：二进制第 i 位是 1，表示选了第 i 株。
#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T, m;
    cin >> T >> m;
    vector<int> t(m), v(m);  // 从 0 开始编号，第 i 株对应二进制的第 i 位
    for (int i = 0; i < m; i++) cin >> t[i] >> v[i];
    long long best = 0;
    for (int mask = 0; mask < (1 << m); mask++) {  // 枚举每一个子集
        long long used = 0, gain = 0;
        for (int i = 0; i < m; i++)
            if (mask >> i & 1) {  // 第 i 位是 1：这个子集里有第 i 株
                used += t[i];
                gain += v[i];
            }
        if (used <= T) best = max(best, gain);  // 合法的子集才用来更新答案
    }
    cout << best << '\n';
    return 0;
}

// 排列枚举（next_permutation）。用洛谷 P1171 售货员的难题的输入格式，演示 n ≤ 10 时的暴力：
// n 个村庄，d[i][j] 是从 i 到 j 的路程。从 1 号出发，每个村庄恰好去一次，最后回到 1 号，求最短总路程。
#include <bits/stdc++.h>
using namespace std;

int n, d[25][25];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++) cin >> d[i][j];
    vector<int> order;  // 2..n 号村庄的访问顺序；起点固定，不参与排列
    for (int i = 2; i <= n; i++) order.push_back(i);
    long long best = LLONG_MAX;
    do {  // 数组一开始是升序（最小的排列），这样才能枚举到全部 (n-1)! 种
        long long len = 0;
        int cur = 1;
        for (size_t i = 0; i < order.size(); i++) {
            len += d[cur][order[i]];
            cur = order[i];
        }
        len += d[cur][1];  // 别忘了回到起点的那一段
        best = min(best, len);
    } while (next_permutation(order.begin(), order.end()));  // 换成下一个排列；没有下一个了就返回 false
    cout << best << '\n';
    return 0;
}

// DFS 回溯与剪枝。洛谷 P1219 [USACO1.5] 八皇后 Checker Challenge：
// n×n 的棋盘上放 n 个皇后，任意两个不同行、不同列、不在同一条斜线上。
// 输出字典序最小的前 3 个方案（第 i 个数是第 i 行的皇后所在的列）和方案总数。
#include <bits/stdc++.h>
using namespace std;

int n, total;
int pos[15];                         // pos[r]：第 r 行的皇后放在第几列
bool col[15], diag1[30], diag2[30];  // 这一列、这条“/”斜线、这条“\”斜线上是否已经有皇后

void dfs(int r) {  // 前 r - 1 行已经放好，现在决定第 r 行
    if (r > n) {   // n 行都放完了：找到一个方案
        total++;
        if (total <= 3) {
            for (int i = 1; i <= n; i++) cout << pos[i] << ' ';
            cout << '\n';
        }
        return;
    }
    for (int c = 1; c <= n; c++) {  // 依次尝试第 r 行的每一列
        if (col[c] || diag1[r + c] || diag2[r - c + n]) continue;  // 剪枝：会冲突的位置直接跳过
        pos[r] = c;
        col[c] = diag1[r + c] = diag2[r - c + n] = true;   // 占用
        dfs(r + 1);
        col[c] = diag1[r + c] = diag2[r - c + n] = false;  // 回溯：撤销占用，再试下一列
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n;
    dfs(1);
    cout << total << '\n';
    return 0;
}

void dfs(int step) {                       // 前 step - 1 个决定已经做完
    if (step > n) { 检查、更新答案; return; }
    for (第 step 个决定的每一种选择) {
        if (现在就能看出这种选择不行) continue;   // 剪枝
        做出选择（修改状态）;
        dfs(step + 1);
        撤销选择（把状态改回去）;               // 回溯
    }
}

// BFS 求网格上的最少步数。洛谷 P1443 马的遍历：
// n×m 的棋盘，马从 (x, y) 出发，输出它到每个格子最少要走几步，到不了的格子输出 -1。
#include <bits/stdc++.h>
using namespace std;

const int N = 405;
const int dx[8] = {1, 2, 2, 1, -1, -2, -2, -1};  // 马的 8 种走法。走迷宫时换成上下左右 4 种
const int dy[8] = {2, 1, -1, -2, -2, -1, 1, 2};
int n, m, dist[N][N];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int sx, sy;
    cin >> n >> m >> sx >> sy;
    memset(dist, -1, sizeof(dist));  // -1 表示还没到过
    queue<pair<int, int> > q;
    dist[sx][sy] = 0;  // 入队的同时就写上步数，它也充当“已访问”的标记
    q.push(make_pair(sx, sy));
    while (!q.empty()) {
        int x = q.front().first, y = q.front().second;
        q.pop();
        for (int k = 0; k < 8; k++) {
            int nx = x + dx[k], ny = y + dy[k];
            if (nx < 1 || nx > n || ny < 1 || ny > m) continue;  // 先查出界
            if (dist[nx][ny] != -1) continue;                    // 再查到没到过（第一次到就是最少步数）
            dist[nx][ny] = dist[x][y] + 1;
            q.push(make_pair(nx, ny));
        }
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) cout << left << setw(5) << dist[i][j];  // 题目要求左对齐、宽 5 格：left 是左对齐，setw(5) 是占 5 格
        cout << '\n';
    }
    return 0;
}

// 记忆化搜索。洛谷 P1434 [SHOI2002] 滑雪：
// R 行 C 列的高度表，每次只能滑到上下左右相邻且更低的格子，求最长的一条路线经过多少个格子。
#include <bits/stdc++.h>
using namespace std;

const int N = 105;
const int dx[4] = {1, -1, 0, 0}, dy[4] = {0, 0, 1, -1};
int R, C, h[N][N];
int f[N][N];  // f[x][y]：从 (x, y) 出发最多能经过几个格子。0 表示还没算过（真实答案至少是 1）

int dfs(int x, int y) {
    if (f[x][y]) return f[x][y];  // 算过了就直接用。少了这一行，同一个格子会被重复计算无数次
    int best = 1;                 // 至少包括自己这一格
    for (int k = 0; k < 4; k++) {
        int nx = x + dx[k], ny = y + dy[k];
        if (nx < 1 || nx > R || ny < 1 || ny > C) continue;
        if (h[nx][ny] < h[x][y]) best = max(best, dfs(nx, ny) + 1);  // 只能往更低处滑，所以不会绕回来
    }
    return f[x][y] = best;  // 先记下来，再返回
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> R >> C;
    for (int i = 1; i <= R; i++)
        for (int j = 1; j <= C; j++) cin >> h[i][j];
    int ans = 0;
    for (int i = 1; i <= R; i++)
        for (int j = 1; j <= C; j++) ans = max(ans, dfs(i, j));  // 起点任选，每个格子都试一遍
    cout << ans << '\n';
    return 0;
}

while (uu < n) {
    uuu = uu; uu = ft[uu]; m++;      // ft[uu]：从 uu 出发最远能到的岛
    for (int i = uuu + 1; i <= uu; i++) dis[u][i] = m;
}