题目大意
给出序列p和实数k
遍历p每次更新r为
可以放弃m个位置,求最后r的max
性质
因为 0.1<=k<=1
所以 r的系数最大为0.9
p<=1e5
所以设0.9^k*1e5=1e-9
所以 大约310次后最开始的r的影响是1e-9,误差范围1e-9,所以310次后最开始的r就没用了
思路
我们只需要考虑最靠后的310次rated比赛
因为前面的没用,显然是把m保留到最后
可知最后m+310个p才是有用的
若n>=m+310,就看最后m+310个p
若n<m+310,就看所有的
然后直接dp,dp[i][j]表示选到第i场,选了j个的最大r
初始值可以是任意数,因为初始值的影响会在310次后消失
时间复杂度O(nT+90000T) 1e8左右