我？场切黑？真的假的？

AVENGER_M · 2025-10-16 15:34:58 · 题解

前言

noip 模拟赛 T2 放这种题，出题人你这辈子有了。

noip 模拟赛 T2，场上 130 个人中过了 20 多个。

观察

首先注意到操作是可逆的。并且，如果有 x 个生物闯入了一个房间，并带着 y(y\ge x) 个生物回到这个房间，那么这 y 个生物也能闯回去。

其次我们注意到，这个问题等价于安放尽可能多的生物，使得没有任何一个生物可以到达自己起点更靠左的地方（或者离开）。

再其次我们注意到值域很小。

解法

如果我们钦定了前几个房间的生物单靠自己无法往左移动，那么它们肯定会往右侧 rush，试图解救右侧房间的生物并原路返回。

考虑动态规划。设 f_{i,j} 为对于前 i 个房间，在没有生物可以往左走且最大有 j 个生物可以聚集在第 i 个房间的情况下，这些房间总共最多可以放多少个生物（无解记为 -\infin）。

边界为 \forall 0\le j<m,f_{1,j}=j 以及 \forall m\le j,f_{1,j}=-\infin。

接下来对于 \forall 1\le i<n，设 x,z 为第 i,i+1 个房间内最多聚集的生物数，y 为第 i+1 个房间内的生物数，则：

• 显然 y\le b_i。

• 如果 x<a_i，那么：

  • 若 y<b_i，则左边的生物过不来，z=y。
  • 若 y=b_i，则左边的生物能过来，z=x+y。

• 如果 a_i\le x<a_i+b_i，那么 y=0，不然这边的生物就往左走了。同时，左边会留下 a_i 个生物，并且使其它的生物闯入右边，z=x-a_i。

• 如果 x\ge a_i+b_i，那么 y=0，且左边的生物全部可以闯入右边，z=x。

记 A 为值域。注意到在合法的情况下最多聚集 2A 个生物，那么分讨并 dp 即可。时间复杂度 O(nA)。

代码

代码非常短。

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

int cid,T,n,m,a[2005],b[2005];
int M=40000,f[40005],g[40005];

int main(){
    cin>>n>>m;m--;
    for(int i=1;i<n;i++)cin>>a[i]>>b[i];
    memset(f,0xb0,sizeof(f));memset(g,0xb0,sizeof(g));
    for(int j=0;j<=M;j++)f[j]=(j<=m?j:0xb0b0b0b0);
    for(int i=1;i<n;i++){
        for(int j=0;j<=M;j++)g[j]=f[j];
        for(int j=b[i];j<a[i]+b[i];j++)f[j]=max(f[j],g[j-b[i]]+b[i]);
        for(int j=a[i];j<a[i]+b[i];j++)f[j-a[i]]=max(f[j-a[i]],g[j]);
        int mxm=0xb0b0b0b0;for(int j=0;j<a[i];j++)mxm=max(mxm,g[j]);
        for(int j=0;j<b[i];j++)f[j]=max(f[j],mxm+j);
    }
    int ca=0xb0b0b0b0;for(int j=0;j<=M;j++)ca=max(ca,f[j]);
    cout<<ca<<'\n';
    return 0;
}