Codeforces Round #711 Bananas in a Microwave 阅读理解题

题意

此题的难点主要在于题意……以下内容全为意译。

你有$m$根香蕉，你的目的是在n次操作后，问每根香蕉最早可能被操作的时间。（其中假设有一根0号香蕉，已经被处理过了，之后不用输出这个香蕉。也就是$k=0$。）

每次操作，给你一个$t$表示步骤的类型，给你一个$x$后面步骤里有用。给你一个$y$，表示当前操作内可以执行最多$y$次下述步骤。

步骤有两类：

1. 第一类，选择一个已经操作过的香蕉$k$，可以操作第$\lceil{k+x}\rceil$号香蕉。
2. 第二类，选择一个已经操作过的香蕉$k$，可以操作第$\lceil{k\cdot{x}}\rceil$号香蕉。

题解

就一个很水的DP。

定义$next$是根据$t$计算得到相应的下标。如$\lceil{i+x}\rceil$和$\lceil{i\cdot{x}}\rceil$。

对于第$cas$次操作，如果$ans[i]\neq{-1}$且$used[i]<y$，我们有$ans[next]=cas$且$used[next]=used[i]+1$。（注意每次操作$used$都会被重置）

扫描和更新$ans$与$used$。扫描的顺序是从左往右还是从右往左取决于$next$和$i$的大小关系。

没了。难点全在题意理解上。

代码