【题解】CF1491C Pekora and Trampoline

题目

CF1491C Pekora and Trampoline

题解

贪心策略:尽量从编号小的地方开始跳。

从头到尾模拟跳的过程,但是如果对每一步都逐个模拟会超时。可以发现:每次在一个地方跳的时候,只会影响到它后面的物体,而对前面的无影响。所以,处理某一点时,可以先将影响传递到下一点,不必传递到结尾。因此,需要记录每一点被前面的路线经过了几次。对于某一点,如果要使它的值降为1,则一定会经过i+2~i+S[i]的每一点,并且,如果这点的值为1后又被经过了几次,则i+1也会同样被影响。

代码

Subscribe
提醒
guest
1 评论
Oldest
Newest Most Voted
Inline Feedbacks
View all comments
cyx
cyx
2021年3月2日 上午11:29

【小白解析】
贪心思想为此题关键,具体体现为:

尽量从编号小的地方开始跳。

从更左侧起跳,确保起跳过程的影响覆盖的蹦床数量更大。
具体实现中,内层循环负责计算从给定蹦床i起跳时,每一步的覆盖面积。要使该蹦床的Si降为1,需使得其经历Si, Si-1, Si-2, … 2, 1的变化。每一步变化中,蹦床i右侧Si位(即整体的i+Si),Si-1位(i+Si-1),…2位(i+2)各经历一次落脚与起跳,即:

对于某一点,如果要使它的值降为1,则一定会经过i+2~i+S[i]的每一点

代码实现为:

for(int j=i+2;j<=min(n,i+s[i]);j++) step[j]++;

其中j负责遍历蹦床右侧所有经过的蹦床。
随后需要考虑该蹦床i是否在Si=1的情况下,于之前的遍历过程中经历多次落脚与起跳(即i+1位置的蹦床是否多次被经过):

step[i+1]+=max(0,step[i]s[i]+1);

当经过i的次数正好为s[i]时,i+1正好被经过一次,故max函数中的二参数需要+1。
最后统计此轮中需要经过i的次数(即Si减去之前所有轮次中已经过的次数,再-1确保Si停留再1),更新ans:

ans+=max(0,s[i]step[i]1);

外层循环负责从左往右遍历每一张蹦床:

for(int i=1;i<=n;i++)

*Trampoline似乎是R语言封装过程中的一个奇妙术语,负责调用内部函数。