AT abc458 G - Children Yearn for the Evil Kindergarten 题解

· · 题解

这道题把我困扰了好久，然后写这篇题解的当天下午发现自己理解错题了。然后就会了这种写法。

本写法为 slope trick + deque 优化，线性。听说有二分、贪心的做法，可以参考官方题解。这里就不做赘述了。

换一个角度考虑问题，即我们可以把这个看起来有点复杂的规划问题转换成“填小孩”这里用词是不是有点不当的问题，即在奖牌形态固定的情况下，每个小孩在第 i 天 escape 的代价为 b_1+b_2+\dots+b_{i-1}+(b_i+c_i)。看起来似乎可以动态规划。这里的 i 个加项分别依次对应第 1 天到第 i 天的代价。注意这里第 j 天的奖牌第 j 天到第 n 天都能使用，所以要加一维奖牌数。

那么现在我们梳理一下 dp 维度，天数一维，小孩总数一维，小孩结束个数一维，转移一维，奖牌一维，哇似乎是五维的，把奖牌一维固定下来即维护每个状态最小消耗奖牌数也是四维的，这也太不好做了。唉，正难则反嘛，我们倒过来遍历，对于结束个数和总数就可以当做是同一维度的了。即，当前只需要知道第 i 天及以后结束的小朋友个数，对于前面结束的小朋友是之后遍历的内容，暂时不用管。那么就可以消掉一维啦！

现在得到一个状态 O(n^2) ，时间 O(n^3) 的做法，对于 f_{i,j} 表示第 i 天以后共有 j 个小朋友 escape，还需要从前 i-1 天里面借的最少奖牌数。注意转移的时候第 i 天可能有若干个小朋友结束，所以时间多了一维。

我们发现这就是个最优化取 k 物品价值和问题，不难证明 f_i 函数是单调递增且下凸的。所以我们考虑 slope trick。先推导出题目条件和约束：

我们注意到对于第三条而言相当于和一条直线做 (\min,+) 卷积，第二条是整体平移然后局部清零，第一条相当于是和 l:y=(\sum_{1\le p\lt i-1}a_p)x 取 \max。于是我们想到取维护斜率，然后做区间覆盖，维护区间值并支持查询与线任意一条线段 x 固定的大小。当然用线段树上二分是可以的，不过用 deque 维护同斜率线段可以做到线性。

ps：其实我之前把题目理解成少于 b_i 的小朋友奖牌清零而不用 drop out，这似乎就可以用一个单调栈去维护了，反而更简单。

ll solve(){
    int n=read(),m=1e6+1;
    REP(i,1,n)a[i]=read(),b[i]=read()+b[i-1],c[i]=read(),A[i]=A[i-1]+a[i];
    deque<pl>q; // length and slope
    PER(i,n,1){
        ll v=b[i]+c[i];
        int sum=m*(i==n);
        while(!q.empty()&&q.back().se>=v){
            sum+=q.back().fi;
            q.pop_back();
        }
        if(sum)q.push_back(mkp(sum,v));
        sum=0;
        while(a[i]){
            ll x=q.front().fi,y=q.front().se;
            q.pop_front();
            if(x*y<=a[i]){
                a[i]-=x*y;
                sum+=x;
                continue;
            }
            ll s=x*y-a[i];
            sum+=x-s/y-(s%y>0);
            if(s>=y)q.push_front(mkp(s/y,y));
            if(s%y)q.push_front(mkp(1,s%y));
            break;
        }
        if(sum)q.push_front(mkp(sum,0));
        sum=0;v=0;
        while(!q.empty()&&(!sum||b[i-1]*sum>v)){
            ll x=q.front().fi,y=q.front().se;
            if(!sum&&y>=b[i-1])break;
            if(b[i-1]*(sum+x)>=v+x*y){
                sum+=x;
                v+=x*y;
                q.pop_front();
                continue;
            }
            ll val=(b[i-1]*sum-v)/(y-b[i-1]);
            sum+=val;
            q.front().fi-=val;
            v+=y*val;
            if(b[i-1]*sum==v)continue;
            if(q.front().fi==1)q.front().se-=b[i-1]*sum-v;
            else{
                q.front().fi--;
                q.push_front(mkp(1,y-(b[i-1]*sum-v)));
            }
            break;
        }
        if(sum)q.push_front(mkp(sum,b[i-1]));
    }
    return q.front().fi*(!q.front().se); // remember to update
}

如果有误，或者更好的解法，欢迎私信骚扰。