题目大意

有 $L$ 个地区排成一行，每个地区 $i$ 有一个医院容量 $C_i$。
有 $N$ 个患者依次出现，第 $j$ 个患者出现在道路 $X_j$（连接地区 $X_j$ 和 $X_j+1$）。
处理规则：

• 患者必须被送到道路两端的某个医院住院（如果该医院还有空位）。
• 如果两端医院都有空位，可以任意选择。
• 如果两端医院都满，则用直升机送到岛外。

目标：通过合理选择住院分配（当两边都空时），最大化被直升机送走的人数。

问题转化

定义匹配：一个患者能被安排住院。
我们要求的是最小可能的匹配数，因为：

[ \text{直升机人数} = N - \text{匹配数} ]

要最大化直升机人数，就要最小化匹配数。

思路分析

核心观察

• 患者 $j$ 只能匹配到地区 $X_j$ 或 $X_j+1$。
• 每个地区 $i$ 最多能匹配 $C_i$ 个患者。
• 患者按顺序到达，但我们可以自由选择分配（当两边都空时），因此问题等价于在二分图中求最小匹配数。

动态规划方法

设 $f[i][j][k]$ 表示处理到地区 $i$ 时，地区 $i-1$ 的“剩余未匹配容量”状态为 $j$，地区 $i$ 的“剩余未匹配容量”状态为 $k$ 时的最小匹配数（或最大未匹配数）。
但直接三维状态太大，需要优化。

优化思路

代码中采用的状态设计：

• 对每个地区 $i$，记录所有可能匹配到它的患者列表 $G[i]$（按出现时间排序）。
• $d[i] = |G[i]|$ 表示可能匹配到地区 $i$ 的患者总数。
• $R[i] = d[i] - C[i]$ 表示地区 $i$ 最多能拒绝的患者数（即强制不匹配的数量）。

状态 $f[j][k]$ 表示在地区 $i-1$ 的拒绝模式为 $j$，地区 $i$ 的拒绝模式为 $k$ 时的最大未匹配数。

代码解析

#include <bits/stdc++.h>
#define LL long long
#define sz(x) ((int)x.size())
#define all(x) x.begin(),x.end()
#define fr(x) freopen(#x".in","r",stdin);freopen(#x".out","w",stdout);
using namespace std;
const int N = 8005, inf = 2e9;
int n, m, c[N], C[N], X[N], R[N], ans, d[N];
basic_string<int>G[N];
vector<vector<int>>f, F, g;

inline void cmx(int &x, int y) {
    x = max(x, y);
}

inline int W(int i, int x) {
    return lower_bound(all(G[i]), x) - G[i].begin();
}

int main() {
    cin.tie(0)->sync_with_stdio(0);
    cout.tie(0);
    cin >> n;

    for (int i = 1; i <= n; i++)
        cin >> C[i], G[i] = {0};  // G[i] 存储可能匹配到地区 i 的患者编号

    cin >> m;

    for (int i = 1; i <= m; i++)
        cin >> X[i], G[X[i]] += i, G[X[i] + 1] += i;  // 患者 i 可能去 X[i] 或 X[i]+1

    for (int i = 1; i <= n; i++) {
        sort(all(G[i]));  // 按患者出现时间排序
        C[i] = min(C[i], (d[i] = sz(G[i])) - 1);  // 容量不超过可能患者数
        R[i] = d[i] - C[i];  // 最多能拒绝的患者数
    }

    // f[J][K] 表示地区 i-1 拒绝 J 个，地区 i 拒绝 K 个时的最大未匹配数
    f = vector<vector<int>>(R[1], vector<int>(R[1], -inf));

    for (int J = 0; J < R[1]; J++)
        f[J][J] = 0;  // 初始化

    for (int i = 2, V; i <= n; i++) {
        g = F = vector<vector<int>>(R[i], vector<int>(R[i], -inf));

        // 前缀和：c[j] 表示前 j 个患者中有多少在道路 i-1 上
        for (int j = 1; j <= m; j++)
            c[j] = c[j - 1] + (X[j] == i - 1);

        // 情况1：地区 i-1 拒绝所有可能患者
        if (R[i - 1] >= 1) {
            int j = d[i - 1] - 1, _j = j - C[i - 1];
            for (int k = 0; k < R[i - 1]; k++)
                if ((V = f[_j][k]) >= 0)
                    for (int J = 0; J < R[i]; J++)
                        cmx(F[J][J], V + c[m] - c[max(G[i - 1][j], G[i][J + C[i]])]);
        }

        // 情况2：地区 i 拒绝所有可能患者
        if (R[i] >= 1) {
            int J = R[i] - 1;
            for (int j = C[i - 1]; j < d[i - 1] - 1; j++)
                for (int k = 0; k < R[i - 1]; k++)
                    if ((V = f[j - C[i - 1]][k]) >= 0)
                        cmx(F[J][J], V + c[m] - c[max(G[i - 1][j], G[i][J + C[i]])]);
        }

        // 情况3：部分拒绝，部分接受
        for (int j = C[i - 1]; j < d[i - 1] - 1; j++) {
            int x = G[i - 1][j], p = W(i, x);  // 患者 x 在地区 i 中的位置
            for (int k = 0; k < R[i - 1]; k++)
                if ((V = f[j - C[i - 1]][k]) >= 0) {
                    int D = min(0, k - c[x]), l = max(p, C[i] - D) - C[i];
                    if (l + C[i] < d[i] - 1)
                        cmx(g[l][l + D], V);
                }
        }

        // 前缀最大值优化
        for (int j = 1; j < R[i] - 1; j++)
            for (int k = 1; k < R[i]; k++)
                cmx(g[j][k], g[j - 1][k - 1]);

        for (int j = 0; j < R[i] - 1; j++)
            for (int k = 0; k < R[i]; k++)
                cmx(F[j][k], g[j][k] + c[m] - c[G[i][j + C[i]]]);

        // 另一种转移：从地区 i-1 的剩余状态转移
        g = vector<vector<int>>(R[i - 1], vector<int>(R[i - 1], -inf));
        for (int j = R[i - 1] - 2; j >= 0; j--)
            for (int k = 0; k < R[i - 1]; k++)
                g[j][k] = max(g[j + 1][k], f[j][k] + c[m] - c[G[i - 1][j + C[i - 1]]]);

        for (int J = C[i]; J < d[i] - 1; J++)
            for (int k = 0; k < R[i - 1]; k++) {
                int K = min(0, k - c[G[i][J]]) + J - C[i];
                if (K < 0) continue;
                int p = max(C[i - 1], W(i - 1, G[i][J] + 1)) - C[i - 1];
                if (p < R[i - 1] - 1)
                    cmx(F[J - C[i]][K], g[p][k]);
            }

        swap(f, F);  // 滚动数组
    }

    // 最终答案取最大值
    for (int i = 0; i < R[n]; i++)
        for (int x : f[i])
            cmx(ans, x);

    cout << ans;
    return 0;
}

复杂度分析

• 预处理：$O(N + L \log N)$
• 动态规划：最坏 $O(L \cdot R^3)$，但实际由于 $R[i] \leq m$ 且剪枝，可运行在 $L \leq 8000$ 的数据范围内。

总结

本题通过将问题转化为二分图最小匹配，并利用患者按道路分布的局部性，设计出基于“拒绝数”的状态转移，最终用动态规划求解。
代码实现较为复杂，但核心思想是最大化未匹配数，即最小化实际住院人数。