题解：P10627 [JOI Open 2024] 中暑 / Heat Stroke

· · 题解

给定 n 个盒子，第 i 个盒子容量为 C_i。

然后依次给出 m 个球，第 i 个球可以放到 X_i 或 X_i + 1 号盒子，如果两个盒子都满了就丢弃，求最多可能丢弃多少个球。

这题 JOI 场上零个人通过！

本文参考补充了 DaiRuiChen007 的题解。

考虑经典套路：把盒子 i​ 恰好满的时刻 t_i 设出来。

则丢弃的个数 \text{num}=\sum\limits_{i=1}^m [i>\max(t_{X_i},t_{X_i+1})].

考虑一个 t 数组在什么时候成立。

建立二分图，左部点是所有球，右部点是 C_1,C_2,\cdots,C_n 这些组，描述每个盒子。

然后 i\le t_{X_i} 时候 i 和组 X_i 的这 C_{X_i} 个点全部连边。i 与 X_{i+1} 同理。

此时等价于一个完美匹配右部组的问题。考虑应用 Hall 定理。

Hall 定理啥时候只需要考虑区间？

二分图一侧顶点集 Y 可以被恰当排序，使得另一侧 X 的每一个顶点 x 的邻居集合 N(x) 都是 Y 中一段连续的区间时。

于是这题只需要考虑右部点的区间 |N(S)|\ge |S|.

\\ \left\vert\bigcup\limits_{i\in [l,r]} \{j:j\le t_i,X_j\in \{i-1,i\}\}\right\vert\ge \sum\limits_{i\in [l,r]} C_i

考虑计算 r-1\to r 的变化量，因为变化量是相对固定的。考虑对于固定的 r 记录 \min (\vert|N([l,r])|-|[l,r]|)，则始终要求这个 \min\ge 0.

记原来的 \min=k，c_1 表示 j\le \min(t_{r-1},t_{r}),X_j=r-1 的个数，c_2 表示 j\le t_r,X_j\in \{r-1,r\} 的个数。

变化为 k'\gets \min(k-c_1,0)+c_2-C_{i}.

在 dp 的过程中记录后缀最小值：记 f_{i,j,k} 表示 r\le i 之前的区间的合法，t_i=j，那个 \min=k 的最大丢弃个数。

注意到 j 一定是某个 X_t \in \{j-1,j\} 的 t，设这样的 t 总数为 s_i，则 k \le s_i - C_i。

因为 \sum s_i=\mathcal{O}(m)，所以状态总数 \le \sum s_i^2 = \mathcal{O}(m^2)。

相当于把这 s_i 个点离散下来，然后再 dp 转移。

转移时就枚举 j' 算出 (j,k) \to (j',k') 的增量，此时复杂度 \mathcal{O}(m^3)。

于是写出一份 优美的 \mathcal{O}(m^3) 代码，由于这东西卡不满获得 95 分的高分。

不理解上面内容的建议严肃观看这个三方代码，对辅助理解起到了极大作用。

判掉 t_{i-1},t_i=\infty 的转移，发现转移只在 j' < j 和 j \le j' 两种情况有较大区别，对于这两部分都能做个后缀 \max 啥的优化到 \mathcal{O}(m^2)。

时间复杂度 \mathcal{O}(nm + m^2)，轻松通过。

:::info[代码]

#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};cin>>m; 
    for(int i=1;i<=m;i++) cin>>X[i],G[X[i]]+=i,G[X[i]+1]+=i;
    for(int i=1;i<=n;i++) C[i]=min(C[i],(d[i]=sz(G[i]))-1),R[i]=d[i]-C[i];
    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));
        for(int j=1;j<=m;j++) c[j]=c[j-1]+(X[j]==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]])]);
        }
        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]])]);
        }//两个 inf 的转移
        for(int j=C[i-1];j<d[i-1]-1;j++)
        {
            int x=G[i-1][j],p=W(i,x);
            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]);//斜线 max
        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]]]);
        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]]]);//后缀 max
        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;
}

:::