25 · 回顾五：递归与 DFS

递归函数 readStr() 的语义是：从当前读位置开始，读一段内容，读到配对的 ] 或输入末尾为止，返回这段内容。

循环读字符，三种情况：普通字母 → 直接接在结果后面；[ → 读整数 D，递归读出子串 t，把 t 重复 D 次接上；] → 本层读完，return。

出口有两个：读到 ]（这一层结束）和读到输入末尾（最外层结束）。

为什么这样一定对：左括号和右括号严格配对，递归进入一层就消耗掉一个左括号，返回时刚好消耗掉配对的右括号，流的位置自然停在括号后面，外层接着往下读。

复杂度：每个字符只被读一次，拼接总量等于输出长度，总时间 O(输出长度)。

#include <bits/stdc++.h>
using namespace std;

// 从当前读位置读一段，读到配对的 ']' 或输入结束为止
string readStr() {
    string s;
    char c;
    while (cin >> c) {                  // 一次读一个字符
        if (c == '[') {                 // 遇到左括号：后面紧跟重复次数
            int k = 0;
            cin >> k;                   // 读整数，正好停在内容第一个字符上
            string t = readStr();       // 递归读括号里的内容
            while (k--) s += t;         // 重复 k 次（k-- 是先用后减）
        } else if (c == ']') {          // 出口：这一层结束
            return s;
        } else {
            s += c;                     // 普通字母：直接接上
        }
    }
    return s;                           // 最外层读到输入结束也要返回值
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout << readStr() << "\n";
    return 0;
}

状态：dfs(x, y, sum) 表示正在决定第 x 行第 y 列，已取数字之和是 sum。

分支：不取 → 直接走到下一个格子；取 → 先检查 4 个已处理方向的邻格，没冲突才标记并累加。

出口：走完最后一行时用 sum 更新 best。

剪枝：预处理 suf[x][y] = 从 (x,y) 按行序到末尾的所有数字之和。若 sum + suf[x][y] <= best，后面的格子全取也不可能更好，直接 return。

为什么只查 4 个方向：行序遍历时，右、左下、下、右下都还没决定，不可能与当前格冲突。

规模：6×6 网格的独立集约 5.6×10⁶ 个，比 2³⁶ = 6.9×10¹⁰ 小得多；再加后缀和剪枝，T ≤ 20 也很快。

#include <bits/stdc++.h>
using namespace std;

int T, n, m;
int a[8][8];
bool used[8][8];
int suf[8][8];              // suf[x][y]：从 (x,y) 按行序到末尾的所有数字之和
int best;

// 按行序处理时，只需要检查已经决定过的 4 个方向
const int dx[4] = {0, -1, -1, -1};
const int dy[4] = {-1, -1, 0, 1};

bool canTake(int x, int y) {
    for (int k = 0; k < 4; ++k) {
        int nx = x + dx[k], ny = y + dy[k];
        if (nx < 1 || nx > n || ny < 1 || ny > m) continue;
        if (used[nx][ny]) return false;          // 和已选的格子相邻，不能取
    }
    return true;
}

void dfs(int x, int y, int sum) {
    if (x > n) {                                 // 出口：所有格子都决定完了
        best = max(best, sum);
        return;
    }
    if (sum + suf[x][y] <= best) return;         // 剪枝：后面全取也超不过当前最优

    int nx = x, ny = y + 1;                      // 下一个格子（到行末就换行）
    if (ny > m) { nx = x + 1; ny = 1; }

    dfs(nx, ny, sum);                            // 分支一：不取当前格
    if (canTake(x, y)) {                         // 分支二：取当前格
        used[x][y] = true;
        dfs(nx, ny, sum + a[x][y]);
        used[x][y] = false;                      // 回溯：还回去
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> T;
    while (T--) {
        cin >> n >> m;
        for (int i = 1; i <= n; ++i)
            for (int j = 1; j <= m; ++j) {
                cin >> a[i][j];
                used[i][j] = false;              // 多组数据：每组都要清空
            }
        memset(suf, 0, sizeof suf);              // 边界 suf[n+1][1] 必须是 0，多组数据要还原
        for (int i = n; i >= 1; --i)             // 从右下往左上递推后缀和
            for (int j = m; j >= 1; --j) {
                int nxt = (j == m) ? suf[i + 1][1] : suf[i][j + 1];
                suf[i][j] = a[i][j] + nxt;
            }
        best = 0;
        dfs(1, 1, 0);
        cout << best << "\n";
    }
    return 0;
}

状态：dfs(x, y, turns, dir) 表示站在 (x,y)，已经转了 turns 次，最后一步的方向是 dir（0 下、1 右）。

分支：向下或向右，各判一次「这一格能不能走」和「换方向后 turns 是否超 K」。

出口：走到 (N,N) 就 ++ans，然后立刻 return。

起点的第一步不算转向，所以先单独迈出第一步（向下或向右），再进入递归。

为什么不会重复计数：只往右下走时，一条路线的方向序列唯一确定这条路线，反过来也唯一，所以枚举方向序列等于枚举路线。

复杂度：K = 3 时合法路线只有 O(N³) 级别，N ≤ 50 时不过十几万条，T ≤ 50 也跑得完。

#include <bits/stdc++.h>
using namespace std;

int T, n, K;
char g[55][55];
long long ans;

// x,y：当前位置；turns：已经转向几次；dir：0 表示上一步向下，1 表示向右
void dfs(int x, int y, int turns, int dir) {
    if (x == n && y == n) { ++ans; return; }      // 出口：到牛棚
    if (x + 1 <= n && g[x + 1][y] == '.') {       // 向下走一格
        int t = (dir == 1) ? 1 : 0;               // 原来向右，现在向下 = 转一次
        if (turns + t <= K) dfs(x + 1, y, turns + t, 0);
    }
    if (y + 1 <= n && g[x][y + 1] == '.') {       // 向右走一格
        int t = (dir == 0) ? 1 : 0;
        if (turns + t <= K) dfs(x, y + 1, turns + t, 1);
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> T;
    while (T--) {
        cin >> n >> K;
        for (int i = 1; i <= n; ++i)
            for (int j = 1; j <= n; ++j) cin >> g[i][j];

        ans = 0;
        if (g[2][1] == '.') dfs(2, 1, 0, 0);      // 第一步向下：前面没有方向，不算转向
        if (g[1][2] == '.') dfs(1, 2, 0, 1);      // 第一步向右：同样不算转向
        cout << ans << "\n";
    }
    return 0;
}

状态：dfs(i, cnt) 表示正在安排第 i 只猫，目前已经租了 cnt 辆车；car[j] 记第 j 辆车的当前载重。

分支：放进某辆还装得下的车；或者新开一辆车。

出口：i > N 时用 cnt 更新答案。

剪枝一（最优性）：cnt >= ans 时直接 return——已经租的车不比已知答案少，后面再完美也不可能更优。

剪枝二（对称性）：如果这只猫放进去之前那辆车是空的，说明前面几辆都装不下它；此时再试其它空车完全是重复枚举，直接 break。

排序：把 C 从大到小排。这是本题能过的关键，不是可有可无的优化。

复杂度：3^18 ≈ 3.9×10⁸ 太大，但排序 + 两条剪枝之后实际搜索量很小，N = 18 稳定通过。

#include <bits/stdc++.h>
using namespace std;

int n, W;
int c[25];
int car[25];              // car[j]：第 j 辆车当前的载重
int ans;

void dfs(int i, int cnt) {              // 安排第 i 只猫，已用 cnt 辆车
    if (cnt >= ans) return;             // 剪枝一：车数已不优于答案，放弃这一支
    if (i > n) {                        // 出口：全部安排完
        ans = cnt;                      // 能到这里的 cnt 一定比 ans 小
        return;
    }
    for (int j = 1; j <= cnt; ++j) {
        if (car[j] + c[i] <= W) {
            car[j] += c[i];
            dfs(i + 1, cnt);
            car[j] -= c[i];             // 回溯：把猫从车上拿下来
            if (car[j] == 0) break;     // 剪枝二：空车彼此等价，不再重复试
        }
    }
    car[cnt + 1] = c[i];                // 新开一辆车
    dfs(i + 1, cnt + 1);
    car[cnt + 1] = 0;                   // 回溯
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n >> W;
    for (int i = 1; i <= n; ++i) cin >> c[i];
    sort(c + 1, c + n + 1, greater<int>());   // 大猫先放，剪枝才狠
    ans = n;                                  // 上界：一只猫一辆车
    dfs(1, 0);
    cout << ans << "\n";
    return 0;
}

预处理：ov[i][j] = 单词 i 的后缀与单词 j 的前缀的最短非空重叠长度，0 表示接不上。对每对单词从小到大枚举 k（1 ≤ k < min(len_i, len_j)），第一个满足「i 的最后 k 个字符 == j 的前 k 个字符」的 k 就是答案。

为什么要最小的 k：接上以后长度增加 len_j - k，k 越小增加越多。

状态：dfs(last, len) 表示当前龙以第 last 个单词结尾，总长度是 len。

每进入一个状态先 ans = max(ans, len)——龙可以随时停下，最长值不一定出现在最后一步。

分支：枚举下一个单词 j，跳过「已用两次」和「接不上」的。

回溯：used[j]++ 后递归，返回后 used[j]--。

起点：枚举所有首字母等于给定字母的单词，把它记为用了一次，从它开始搜。

本题是上古 NOIP 题，数据很弱，朴素回溯就能过；它的难度评级只对应「能通过原始数据」的做法。

#include <bits/stdc++.h>
using namespace std;

int n, ans = 0;
string w[25];
int used[25];              // 每个单词已经用了几次
int ov[25][25];            // ov[i][j]：i 后面接 j 的最短重叠长度，0 表示接不上

// a 的后缀与 b 的前缀的最短非空重叠长度
int overlap(const string &a, const string &b) {
    int la = a.size(), lb = b.size();
    for (int k = 1; k < la && k < lb; ++k) {     // 重叠必须小于任一整词
        bool ok = true;
        for (int t = 0; t < k; ++t)
            if (a[la - k + t] != b[t]) { ok = false; break; }
        if (ok) return k;                        // 第一个合法的 k 就是最短的
    }
    return 0;
}

void dfs(int last, int len) {
    ans = max(ans, len);                         // 每一步都可能是最长
    for (int j = 0; j < n; ++j) {
        if (used[j] >= 2 || ov[last][j] == 0) continue;   // 用满两次 / 接不上
        used[j]++;
        dfs(j, len + (int)w[j].size() - ov[last][j]);     // 重叠部分只算一次
        used[j]--;                                        // 回溯：还回去
    }
}

int main() {
    cin >> n;
    for (int i = 0; i < n; ++i) cin >> w[i];
    char st;
    cin >> st;

    for (int i = 0; i < n; ++i)
        for (int j = 0; j < n; ++j)
            ov[i][j] = overlap(w[i], w[j]);

    for (int i = 0; i < n; ++i)
        if (w[i][0] == st) {                     // 只能从这个字母开头的词起头
            used[i]++;                           // 开头词本身也算用了一次
            dfs(i, (int)w[i].size());
            used[i]--;
        }
    cout << ans << "\n";
    return 0;
}