状态压缩动态规划 与 动态规划的常用优化

for (int S = 0; S < (1 << n); S++) {
    // 处理集合 S
}

for (int T = S; T; T = (T - 1) & S) {
    // T 依次取遍 S 的所有非空子集（从大到小）
}
// 别忘了 T = 0（空集）

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

int n, K;
long long f[12][1 << 10][90];  // f[i][S][t]: 前 i 行、第 i 行状态 S、共 t 个国王的方案数
int cnt[1 << 10];             // cnt[S] = S 中 1 的个数
vector<int> ok;                  // 行内合法的状态列表

int main() {
    cin >> n >> K;
    int FULL = 1 << n;

    // ---------- 第一步：筛出行内合法的状态 ----------
    for (int S = 0; S < FULL; S++) {
        if (S & (S << 1)) continue;      // 行内有相邻的 1，非法
        ok.push_back(S);
        cnt[S] = __builtin_popcount(S);
    }

    // ---------- 第二步：初始化第 1 行 ----------
    for (int S : ok)
        if (cnt[S] <= K) f[1][S][cnt[S]] = 1;

    // ---------- 第三步：按行递推 ----------
    for (int i = 2; i <= n; i++) {
        for (int S : ok) {                  // 本行状态
            for (int P : ok) {              // 上一行状态
                if (S & P) continue;                        // 同列冲突
                if (S & (P << 1)) continue;              // 左上斜冲突
                if (S & (P >> 1)) continue;              // 右上斜冲突
                for (int t = cnt[S]; t <= K; t++)
                    f[i][S][t] += f[i - 1][P][t - cnt[S]];
            }
        }
    }

    // ---------- 第四步：汇总第 n 行的答案 ----------
    long long ans = 0;
    for (int S : ok) ans += f[n][S][K];
    cout << ans << "\n";
    return 0;
}

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

int a[15];              // a[1] 是最低位，a[len] 是最高位
int f[15][13];           // f[pos][last]，last ∈ [0,9] ∪ {11}

// last = 11 表示「前面全是前导零，还没有真正的上一位」
int dfs(int pos, int last, bool limit) {
    if (pos == 0) return 1;                  // 填完了，这一条路径合法
    if (!limit && f[pos][last] != -1) return f[pos][last];

    int up = limit ? a[pos] : 9;          // 当前位能填的最大值
    int res = 0;
    for (int d = 0; d <= up; d++) {
        if (last != 11 && abs(d - last) < 2) continue;   // 与上一位冲突
        int nlast = (last == 11 && d == 0) ? 11 : d;      // 处理前导零
        res += dfs(pos - 1, nlast, limit && (d == up));
    }
    if (!limit) f[pos][last] = res;      // 只有不贴界才缓存
    return res;
}

int solve(int x) {
    if (x <= 0) return 0;
    int len = 0;
    while (x) { a[++len] = x % 10; x /= 10; }
    memset(f, -1, sizeof(f));
    return dfs(len, 11, true) - 1;        // 减去数字 0 自己
}

int main() {
    int A, B;
    cin >> A >> B;
    cout << solve(B) - solve(A - 1) << "\n";
    return 0;
}

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

const int MAXN = 1000006;
int n, k, a[MAXN];
int mn[MAXN], mx[MAXN];       // 答案数组

int main() {
    scanf("%d %d", &n, &k);
    for (int i = 1; i <= n; i++) scanf("%d", &a[i]);

    // ---------- 求最小值：队列内下标对应的值单调递增 ----------
    deque<int> q;
    for (int i = 1; i <= n; i++) {
        while (!q.empty() && q.front() <= i - k) q.pop_front();   // ① 滑出窗口
        while (!q.empty() && a[q.back()] >= a[i]) q.pop_back();   // ② 队尾更大者被压制
        q.push_back(i);                                            // ③ 入队
        if (i >= k) mn[i - k + 1] = a[q.front()];
    }

    // ---------- 求最大值：队列内下标对应的值单调递减 ----------
    q.clear();
    for (int i = 1; i <= n; i++) {
        while (!q.empty() && q.front() <= i - k) q.pop_front();
        while (!q.empty() && a[q.back()] <= a[i]) q.pop_back();   // 注意这里是 <=
        q.push_back(i);
        if (i >= k) mx[i - k + 1] = a[q.front()];
    }

    for (int i = 1; i <= n - k + 1; i++) printf("%d%c", mn[i], " \n"[i == n - k + 1]);
    for (int i = 1; i <= n - k + 1; i++) printf("%d%c", mx[i], " \n"[i == n - k + 1]);
    return 0;
}

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

const int MAXN = 20, INF = 0x3f3f3f3f;
int n, w[MAXN][MAXN];
int f[1 << 18][MAXN];

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

    memset(f, 0x3f, sizeof(f));
    f[1][0] = 0;                        // 初始：只访问了点 0

    int FULL = (1 << n) - 1;
    for (int S = 1; S <= FULL; S++)          // S 从小到大 = 天然拓扑序
        for (int i = 0; i < n; i++) {
            if (!((S >> i) & 1)) continue;    // 当前必须停在 S 里的点上
            if (f[S][i] == INF) continue;     // 不可达，跳过
            for (int j = 0; j < n; j++) {
                if ((S >> j) & 1) continue;       // j 已经访问过，不能再走
                int T = S | (1 << j);
                f[T][j] = min(f[T][j], f[S][i] + w[i][j]);
            }
        }

    int ans = INF;
    for (int i = 0; i < n; i++) ans = min(ans, f[FULL][i]);
    cout << ans << "\n";
    return 0;
}

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

int n, m;
int ban[105];                  // ban[i] 的第 j 位为 1 表示第 i 行第 j 列是山地
int pc[1 << 10];
int f[3][1 << 10][1 << 10];
vector<int> ok;

int main() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        string s; cin >> s;
        for (int j = 0; j < m; j++)
            if (s[j] == 'H') ban[i] |= (1 << j);
    }

    // ---------- 筛出行内合法状态：2 格范围内不能有第二个炮兵 ----------
    for (int S = 0; S < (1 << m); S++) {
        if (S & (S << 1)) continue;      // 相邻列冲突
        if (S & (S << 2)) continue;      // 隔一列冲突
        ok.push_back(S);
        pc[S] = __builtin_popcount(S);
    }

    int ans = 0;
    for (int i = 1; i <= n; i++) {
        int cur = i % 3, p1 = (i - 1) % 3, p2 = (i - 2 + 3) % 3;
        memset(f[cur], 0, sizeof(f[cur]));      // 每行先清空

        for (int S : ok) {                       // 本行状态
            if (S & ban[i]) continue;              // 不能放在山地上
            for (int P : ok) {                   // 上一行状态
                if (S & P) continue;
                for (int Q : ok) {               // 上两行状态
                    if (S & Q) continue;
                    f[cur][S][P] = max(f[cur][S][P], f[p1][P][Q] + pc[S]);
                }
                ans = max(ans, f[cur][S][P]);   // 随时更新全局答案
            }
        }
    }
    cout << ans << "\n";
    return 0;
}

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

const int MAXN = 200005, NEG = -1e9;
int n, L, R, a[MAXN], f[MAXN];

int main() {
    scanf("%d %d %d", &n, &L, &R);
    for (int i = 0; i <= n; i++) scanf("%d", &a[i]);

    for (int i = 0; i <= n; i++) f[i] = NEG;
    f[0] = a[0];                    // 起点

    deque<int> q;                  // 存下标，对应的 f 值单调递减
    for (int i = L; i <= n; i++) {
        // ① 把「新进入窗口」的 i-L 加入队列
        int cand = i - L;
        if (f[cand] > NEG / 2) {
            while (!q.empty() && f[q.back()] <= f[cand]) q.pop_back();
            q.push_back(cand);
        }
        // ② 把「已经滑出窗口」的下标移出（小于 i-R）
        while (!q.empty() && q.front() < i - R) q.pop_front();
        // ③ 队首就是窗口内的最大 f 值
        if (!q.empty()) f[i] = f[q.front()] + a[i];
    }

    int ans = NEG;
    for (int i = max(0, n - R + 1); i <= n; i++) ans = max(ans, f[i]);
    printf("%d\n", ans);
    return 0;
}

// ==================== 模板一：棋盘式状压 DP ====================
int n, m, ban[MAXN], pc[1 << 12];
int f[MAXN][1 << 12];
vector<int> ok;

void init() {
    for (int S = 0; S < (1 << m); S++) {
        if (S & (S << 1)) continue;        // 行内相邻冲突
        ok.push_back(S);
        pc[S] = __builtin_popcount(S);
    }
}

void solve() {
    init();
    for (int S : ok)
        if (!(S & ban[1])) f[1][S] = pc[S];    // 第一行初始化

    for (int i = 2; i <= n; i++) {
        for (int S : ok) {
            if (S & ban[i]) continue;             // 不能用禁用的格子
            for (int P : ok) {
                if (S & P) continue;                 // 同列
                if (S & (P << 1)) continue;           // 左上斜（若题目有斜角约束）
                if (S & (P >> 1)) continue;           // 右上斜
                f[i][S] = max(f[i][S], f[i - 1][P] + pc[S]);
            }
        }
    }
}

// ==================== 模板二：单调队列优化 DP ====================
// f[i] = max{ f[j] } + w(i),  j ∈ [i-R, i-L]
void monoDP() {
    deque<int> q;                        // 存下标，f 值单调递减
    for (int i = L; i <= n; i++) {
        int cand = i - L;
        // ① 补进新候选（跳过不可达状态）
        if (f[cand] > NEG / 2) {
            while (!q.empty() && f[q.back()] <= f[cand]) q.pop_back();
            q.push_back(cand);
        }
        // ② 踢掉过期候选
        while (!q.empty() && q.front() < i - R) q.pop_front();
        // ③ 取队首转移
        if (!q.empty()) f[i] = f[q.front()] + w(i);
    }
}

// ==================== 模板三：数位 DP 记忆化搜索 ====================
int a[20], memo[20][13];
int dfs(int pos, int last, bool limit) {
    if (pos == 0) return 1;
    if (!limit && memo[pos][last] != -1) return memo[pos][last];
    int up = limit ? a[pos] : 9, res = 0;
    for (int d = 0; d <= up; d++) {
        if (last != 11 && abs(d - last) < 2) continue;   // 本题的合法性判断
        int nl = (last == 11 && d == 0) ? 11 : d;
        res += dfs(pos - 1, nl, limit && (d == up));
    }
    if (!limit) memo[pos][last] = res;   // 只有不贴界才缓存
    return res;
}