Children Yearn for the Evil Kindergarten

来源：AT_abc458_g

难度：2831

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

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

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

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

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

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

  • 如果第 ii 天以后共有 jj 个小朋友 escape，那么前 i−1i-1 天剩下留到后面的奖牌数至少是 j∑1≤p<i−1apj\sum_{1\le p\lt i-1}a_p 块。这个信息是最重要的，也是奖牌数个数限制的充要条件。
  • 对于每天新增 aia_i 块奖牌对于 fif_i 的影响是所有元素减去 aia_i 和 00 取 max⁡\max。
  • 对于每多一个小孩，fi,jf_{i,j} 会和 fi+1,j−1+(∑1≤p≤ibp)+cif_{i+1,j-1}+(\sum_{1\le p\le i}b_p)+c_i 取 min⁡\min。

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

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
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
}

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