题意:
* 有 333 道题,每题按过题人数决定分值(500,1000,…,3000500,1000,\dots,3000500,1000,…,3000)。
* 你可以 hack 某些人:每 hack 一次加 100100100 分。
* 每个人某题得分形如:
scorei=xi(250−ti)250score_i=\frac{x_i(250-t_i)}{250} scorei =250xi (250−ti )
求最终排名的最小可能值。
思路要点:
* 总分最大 900090009000,因此 hack 次数最多 909090;
* 能被 hack 的人数量也至多 909090。
* 先枚举每道题的分值(等价于确定每题可 hack 人数),复杂度 O(73)O(7^3)O(73);
* 确定后“hack 越多越好”,你的分数可直接计算;
* 再用 dpi,j,kdp_{i,j,k}dpi,j,k 统计每题 hack 次数固定时,你能达到的最小排名,时间复杂度约为:
O(303⋅90)O(30^3\cdot 90) O(303⋅90)
总体复杂度:
O(73⋅303⋅90)O(7^3\cdot 30^3\cdot 90) O(73⋅303⋅90)