Open OkazakiYumemi opened 4 years ago
https://okazakiyumemi.github.io/blog/AGC044E/
题意简述AGC 044E 给出一个长为 $n$ 的环，每个点有 $a_i, b_i$。随机一个点 $i$ 开始，每次你可以选择停止，则获得当前位置的价值 $a_i$；或者耗费 $b_i$ 的价值，等概率随机移动到左右两点中的一个。 求期望获得的最大价值。$2\le n\le 200000, 0\le a_i\le 10^{12}, 0\le b_i\le 100$。
https://okazakiyumemi.github.io/blog/AGC044E/
题意简述AGC 044E 给出一个长为 $n$ 的环，每个点有 $a_i, b_i$。随机一个点 $i$ 开始，每次你可以选择停止，则获得当前位置的价值 $a_i$；或者耗费 $b_i$ 的价值，等概率随机移动到左右两点中的一个。 求期望获得的最大价值。$2\le n\le 200000, 0\le a_i\le 10^{12}, 0\le b_i\le 100$。