T1：华丽转身

: 1~4 20分

可以观察到数据较小，可以使用 通过（其他乱搞也可）
（为了方便讲解，此处先讲解 ）

: 9~12 另20分

可以发现在权值为1的情况下，可以使用贪心（后文将证明），记录下上一次的名次 ，每次都贪心的尽量让名次最大（即 ），若 ，则说明不管怎样都无法满足条件，则将排名设为
由于贪心遗漏的情况是当 时取 通过舍弃这一次的奖品来使下一次获得奖品，而由于权值全部为1，所以本次贪心所选取的补偿了下一个没取到的，所以贪心正确性可证，时间复杂度

: 5~8 20分（可获得40分）

由上文可知，本题需要使用dp来解决，所以考虑直接设计状态 表示第 场考试考第 名时最多的奖品数，则状态转移方程为:

显然当 一定时， 具有单调性，复杂度

: 13~20 40分（可获得100分）

发现 只有，所以连续获奖的次数最多只有次，同时受上文贪心思想的启发，易发现当本次能获得奖品时取 最优，否则取 最优。则可设计状态 表示第 场考试时已经连续获得了 次奖的最多奖品数，则状态转移方程为

其中 为辅助数组，表示连续去 次奖后第 场考试的最大名次，在转移过程中由上述贪心即可求出 数组，而最大值可在上一轮循环的计算中求出，即 可以 求出，由于每取一次奖，能取得名次都会缩小为原来的一半,即 的规模只有,故复杂度为

：可以使用滚动数组优化空间，本题没有卡空间，所以可以不使用