Readme

2836.Maximize-Value-of-Function-in-a-Ball-Passing-Game

如果不看数据范围，一个比较容易想到的方法就是动态规划。为什么呢？假设dp[i][d]表示以i为起点的、长度为d的序列的value最大值，其中d=1,2,...,k。那么它就依赖于以receiver[i]为起点的、长度为d-1的序列的最大值。继而，依赖于以receiver[receiver[i]]为起点、长度为d-2的序列的最大值。依次类推，对于每个位置i，我们需要按d从小到大依次计算它的dp[i][d].

但在此题中，d的范围是1e10，这样的二维数组无法存下。此时有一个技巧叫做binary lifting，第二个维度只需要存储对数个信息。

具体地，我们令dp[i][j]表示从i开始走2^j步所能得到的最大value。同时辅助pos[i][j]表示从i开始走2^j步所到达的位置。我们用二分来进行状态转移，即找到中点2^(j-1)步后的位置pos[i][j-1]，然后从这里再走2^(j-1)步，故转移方程就有

pos[i][j] = pos[pos[i][j-1]][j-1];
dp[i][j] = dp[i][j-1] + dp[pos[i][j-1]][j-1];

因为我们最多走1e10步，相当于2^34，状态变量里的第二个维度最多34. 我们将j从1到34从小到大进行遍历，根据上面的式子即可顺利填充所有的dp[i][j]和pos[i][j].

最终我们需要考察所有的位置i，看它走k步所能得到的最大value，然后全局取最大值。注意，如果k不是2的次幂的话，我们就没有现成的dp[i][j]作为答案。但是没关系，我们将k进行二进制分解为2^j0+2^j1+2^j2+...后，相当于从i开始先走2^j0步，再走2^j1步，再走2^j2步... 于是我们只需要依次找到这些中继点i,i1,i2,...，将每一段跨度的value累加起来即可，即sum[i] = dp[i][j0] + dp[i1][j1] + dp[i2][j2] + ... . 其中i1=pos[i][j1]，其他的跳转点以此类推。