搜索剪枝 与 记忆化搜索

// ① 容量越界
if (curW + w[i] > cap) continue;          // 装不下，这个选择直接跳过

// ② 整除关系（小木棍的枚举框架）
for (int len = maxLen; len <= sum; len++) {
    if (sum % len) continue;               // ★ 总长必须能被 len 整除
    ...
}

// ③ 剩余最小代价估计（生日蛋糕：上面 dep 层的最小体积）
if (v < minV[dep]) return;                // ★ 体积已经不够放满剩下的层

// ④ 可达性上界（凑目标和的可行性）
if (curSum + restSum < target) return;    // ★ 全加起来都不够，绝无可能

int ans = INF;                       // 全局当前最优解

// 参数：v 剩余体积、s 已用表面积、dep 还要做几层、r/h 下一层的半径与高
void dfs(int v, int s, int dep, int r, int h) {
    if (dep == 0) {
        if (v == 0) ans = min(ans, s);   // 恰好用完体积，更新答案
        return;
    }
    if (v < minV[dep]) return;                 // 可行性：体积不够
    if (s + minS[dep] >= ans) return;            // ★ 最优性：最小侧面积都超了
    if (s + 2 * v / r >= ans) return;           // ★ 最优性：侧面积下界估计 2V/R
    ...
}

// 写法一：记录「上一次失败的值」
int lastFail = -1;
for (int i = st; i <= n; i++) {
    if (a[i] == lastFail) continue;        // ★ 等长的试过一次就够
    ...
    lastFail = a[i];
}

// 写法二：利用排序后的相邻关系（需先按降序排序）
for (int i = st; i <= n; i++) {
    if (vis[i]) continue;
    if (i > 1 && a[i] == a[i - 1] && !vis[i - 1])
        continue;                        // ★ 前一根等长的都没用上，我也别用
    ...
}

// 从 a[st..n] 中继续选数；已选总和为 sum，已选 cnt 个
void dfs(int st, int cnt, int sum) {
    if (cnt == k) {                       // 选够了
        if (sum == target) ans++;
        return;
    }
    if (sum > target) return;                     // ★ 可行性剪枝
    if (sum + suf[st] < target) return;         // ★ 可行性上界：全加上也不够
    for (int i = st; i <= n; i++) {             // ★ 从 st 开始 ⇒ 组合不重复
        if (i > st && a[i] == a[i - 1]) continue;  // ★ 同层去重
        dfs(i + 1, cnt + 1, sum + a[i]);
    }
}

int memo[MAXS];                      // 记忆表
const int UNSEEN = -1;              // 「还没算过」的标记

int dfs(int s) {                       // s 是状态编号（可以是多维）
    if (memo[s] != UNSEEN) return memo[s];   // ★ 第2步：命中缓存直接返回

    if (isBase(s)) return memo[s] = baseValue(s);  // 边界（也要回填）

    int res = initValue;// 例如 0（计数）或 INF（求最小）
    for (每个可达状态 t : nextStates(s))
        res = merge(res, dfs(t) + 1);          // 按题目定义合并

    return memo[s] = res;                // ★ 第3步：先回填，再返回
}

int dfs(int x, int y) {
    if (f[x][y]) return f[x][y];      // ★ 命中缓存：算过就抄
    f[x][y] = 1;                      // 至少包含自己一个格子
    for (int d = 0; d < 4; d++) {
        int nx = x + dx[d], ny = y + dy[d];
        if (nx < 1 || nx > R || ny < 1 || ny > C) continue;
        if (h[nx][ny] < h[x][y])     // 只能往低处滑
            f[x][y] = max(f[x][y], dfs(nx, ny) + 1);
    }
    return f[x][y];                // 回填 & 返回
}

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

int n, sum, maxLen, len, cnt;       // cnt = sum / len，要拼出的根数
int a[70];
bool vis[70];

// k：已拼好 k 根；now：当前这根已拼长度；last：上一次使用的下标
bool dfs(int k, int now, int last) {
    if (k == cnt) return true;                    // 全部拼完，成功
    if (now == len)                              // 这一根拼满了
        return dfs(k + 1, 0, 0);               // 开始拼下一根

    for (int i = last + 1; i <= n; i++) {
        if (vis[i]) continue;
        if (now + a[i] > len) continue;          // ★剪枝③ 放不下
        if (i > 1 && a[i] == a[i - 1] && !vis[i - 1])
            continue;                            // ★剪枝④ 等长不重复试

        vis[i] = true;
        if (dfs(k, now + a[i], i)) return true;
        vis[i] = false;

        if (now == 0) return false;              // ★剪枝⑤ 第一段都失败 ⇒ 无解
        if (now + a[i] == len) return false;     // ★剪枝⑥ 恰好拼满仍失败 ⇒ 无解
    }
    return false;
}

int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        scanf("%d", &a[i]);
        sum += a[i];
        maxLen = max(maxLen, a[i]);
    }
    sort(a + 1, a + n + 1, greater<int>());  // ★剪枝② 降序排序

    for (len = maxLen; len <= sum; len++) {
        if (sum % len) continue;                // ★剪枝① 必须整除
        cnt = sum / len;
        memset(vis, 0, sizeof(vis));
        if (dfs(0, 0, 0)) { printf("%d\n", len); break; }
    }
    return 0;
}

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

int R, C;
int h[105][105];
int f[105][105];                    // memo：0 表示「还没算过」
int dx[4] = {0, 0, 1, -1};
int dy[4] = {1, -1, 0, 0};

int dfs(int x, int y) {
    if (f[x][y]) return f[x][y];          // ★ 命中缓存：算过就直接抄

    f[x][y] = 1;                            // 至少包含自己一个格子
    for (int d = 0; d < 4; d++) {
        int nx = x + dx[d], ny = y + dy[d];
        if (nx < 1 || nx > R || ny < 1 || ny > C) continue;
        if (h[nx][ny] < h[x][y])                // 只能往低处滑（保证无环）
            f[x][y] = max(f[x][y], dfs(nx, ny) + 1);
    }
    return f[x][y];                      // ★ 回填并返回
}

int main() {
    scanf("%d%d", &R, &C);
    for (int i = 1; i <= R; i++)
        for (int j = 1; j <= C; j++)
            scanf("%d", &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));

    printf("%d\n", ans);
    return 0;
}

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

int n;
int memo[105][105];                   // memo[rest][last]，初值 0

// 用不小于 last 的正整数把 rest 拆完的方案数
int dfs(int rest, int last) {
    if (rest == 0) return 1;                // 刚好拆完，记 1 种方案
    if (memo[rest][last]) return memo[rest][last];   // ★ 命中缓存

    int res = 0;
    for (int i = last; i <= rest; i++)          // ★ 范围剪枝：从 last 开始枚举
        res += dfs(rest - i, i);                // 下一个数不能小于 i

    return memo[rest][last] = res;               // ★ 回填并返回
}

int main() {
    scanf("%d", &n);
    printf("%d\n", dfs(n, 1) - 1);          // 减去「整段不拆」这一种
    return 0;
}

void dfs(int step, /* 状态参数 */) {
    // ── 1. 到达终点：更新答案／输出 ──
    if (step == target) { updateAnswer(); return; }

    // ── 2. 可行性剪枝（最便宜，放最前）──
    if (违反约束 || 无法达成目标) return;

    // ── 3. 最优性剪枝（需要 bound 估计函数）──
    if (cur + bound(剩余) >= ans) return;   // 求最小值时用 >=

    // ── 4. 枚举分支（顺序：先试约束最强的）──
    for (int i = st; i <= n; i++) {
        if (已使用) continue;
        if (i > st && a[i] == a[i - 1]) continue;   // 同层去重
        mark(i);
        dfs(step + 1, /* 新状态 */);
        unmark(i);
    }
}

int memo[/* 状态维度 */];
const int UNSEEN = -1;              // 哨兵：合法答案取不到的值

int dfs(/* 状态参数 */) {
    int& ans = memo[/* 状态下标 */];
    if (ans != UNSEEN) return ans;   // ★ 第2步：查缓存

    if (/* 边界 */) return ans = /* 边界值 */;   // 边界也要回填

    ans = /* 初值：计数用 0，求最小用 INF */;
    for (每个子状态 t) ans = merge(ans, dfs(t) + cost);
    return ans;                      // ★ 第3步：已通过引用回填
}