更佳的阅读体验：2023 国庆集训 Day 4B 笔记，本文同步发表于 洛谷博客。

以下内容为个人总结，如有错误或您有不同见解，欢迎指出。

单调队列优化 DP

洛谷 P1886 - 单调队列

int a[N];
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);
    cout << a[q.front()] << '\n';
}

洛谷 P2216 - 理想的正方形

洛谷 P2219 - 修筑绿化带

• 求出每一块花园中，花坛应该放在哪里。如果花园的右下角为 $(x, y)$，那么花坛的右下角就应位于 $(x - a + c + 1, y - b + d + 1) \sim (x - 1, y - 1)$ 这个矩形内。
• 求出这个矩形内最小的 $sum$。

求最大全 0 正方形

给定一个 0 / 1 矩阵，求出最大的全为 0 的子正方形，求不带 $\log$ 的做法。

带 $\log$ 的做法：枚举每个点作为左上角，二分正方形边长。

• 令 $f[i][j]$ 表示矩形 $(i, j)$ 位置往下延伸 $0$ 的个数，得到转移方程 $f[i][j] = \begin{cases} 0, a_{i, j} = 1 \\ f[i + 1][j] + 1, a_{i, j} = 0 \end{cases}$。
• 枚举正方形的上边界 $u$，依次从 $1 \sim n$ 枚举正方形的右边界。
• 维护一个左边界的指针，并用单调队列维护左右边界之中的 $f$ 值，需要时刻保证 $r - l + 1 \le \min ⁡f$ 。
• 复杂度为 $O(n^2 )$。

带修版本：洛谷 P4259 - 寻找车位

洛谷 P2254 - 瑰丽华尔兹

• 设 $f[t][i][j]$ 为 $t$ 时刻到达 $(i, j)$ 的最长路程。
• 假如 $t$ 时刻钢琴是往上方滑动，那么 $f[t][i][j] = \max (f[t - 1][i + 1][j] + 1, f[t - 1][i][j])$。往其他方向同理。
• 复杂度为 $O(nmT)$。
• 由于时间可以被分为 $K$ 段，每段滑动方向相同，则可以修改状态，令 $f[k][i][j]$ 为第 $k$ 个时间段结束后到达 $(i, j)$ 的最长路程。
• $f[k][i][j] = \max {f[k - 1][i + s][j] + s), 0 \le s \le t_k}$。使用单调队列优化。
• 复杂度 $O(nmK)$。

// 不考虑障碍 且只考虑向上的转移

for (int k = 1; k <= K; ++k) {
    int t_k;
    for (int j = 1; j <= m; ++j) {
        deque<int> q;
        int g[];
        for (int i = 1; i <= n; ++i) g[i] = f[k - 1][i][j] + i;
        for (int i = n; i; --i) {
            while (!q.empty() && q.front() > i + t_k) q.pop_front();
            while (!q.empty() && g[q.back()] <= g[i]) q.pop_back()
            q.push_back(i);
            f[k][i][j] = g[q.front()] - i;
        }
    }
}

洛谷 P4381 - Island

• 求若干个基环树的直径之和。
• 对于一个基环树，找到它的环，求出环上每个节点 $i$ 环外延伸的最长距离 $d_i$。
• 将长为 $m$ 的环破为长为 $2m$ 的链。如果从节点 $i$ 外面走到节点 $j$ 外面，则距离为 $j - i + d_i + d_j$，同时要求 $i < j < i + n$。使用单调队列优化求解。
• 复杂度为 $O(n)$。

单调队列优化多重背包

一共有 $c_i$ 个 $i$ 号物品，有 $w_i$ 的价值和 $v_i$ 的体积。

洛谷 P5665 - 划分

• 贪心地使最后一段的和尽可能小。
• 不严谨证明：如果最后一段 $[l, r]$ 的和没到达下界，那么可以不断地把 $a_l$ 分给前一段。由于 $s_i < s_{i+1}$，分给前一段的贡献是 $2a_l s_i$，分给后一段的贡献是 $2a_l s_{i+1}$，则分给前一段更优，同时分给前一段也有利于后面的分段。
• 所以设 $f[r]$ 为 $\max⁡ {l-1: 最后一段分成 [l, r] 可行}$，应有 $sum_r - sum_{l-1} \ge sum_{l-1}-sum_{f[l-1]}$，即 $sum_r \ge 2sum_{l-1} - sum_{f[l-1]}$，双指针即可。
• 复杂度为 $O(n)$。

计数 DP

洛谷 P5824 - 十二重计数法

洛谷 P3702 - 序列计数

• 用总方案数去掉不含质数的方案数。
• 分别用 DP 求解，设 $f[i][j]$ 为 $i$ 个数字，和 $\mod p = j$ 的方案数，矩阵快速幂加速。
• 复杂度 $O(p^3 \log⁡ n )$。

洛谷 P3773 - 吉夫特

• 由 Lucas 定理可知 $C_n^m$ 是奇数 $↔(n\&m)=m$。
• 设 $f[T]$ 表示结尾值为 $S$ 的序列个数，转移时枚举子集 $T$，如果 $pos[S] < pos[T]$ 则令 $f[T]$ 加上 $f[S]$。
• 复杂度为 $O(3^w)$。

int a[N], pos[N];

cin >> n;
for (int i = 1; i <= n; ++i) {
    cin >> a[i];
    pos[a[i]] = i;
}

for (int s = VALUE_MAX; s; --s) {
    ++f[s];
    for (int t = (s - 1) & s; t; --t)
        if (pos[s] < pos[t]) f[t] += f[s];
       ans += f[s] - 1;
}

洛谷 P5664 - Emiya 家今天的饭

• 对「每种食材最多在一半菜中」进行容斥。用总的方案数减去某种食材过多的方案数，不会有两种食材同时过多。
• 总方案数易求。
• 枚举过多的食材种类 $t$，设 $f[i][j][k]$ 表示前 $i$ 种烹饪方法，一共做了 $j$ 个菜，其中 $k$ 个使用 $t$ 的方案数。转移时枚举第 $i + 1$ 种烹饪方法是否选用，选用时是否使用 $t$，最后要求 $k > \frac{j}{2}$ 。
• 只需记录 $2k - j$ 的值即可，最后要求此值 $> 0$。
• 复杂度为 $O(n^2 m)$。