《智力竞赛》题目分析

首先我们可以发现，由于每一关需要的分数Ai是固定的，所以如果确定第i关答错了x题，那么最少需要答对的题目数就是max{0, ⌈(Ai-xT)/S}⌉。

为了描述方便我们把这个值记为c[i][x], 即第i关如果答错的题目数是x，那么这一关最少答对的题目数是c[i][x]。

于是这道题实际是让我们决策每一关答错多少题，才能使得在总答题次数不超过M的情况下，总答对的题目数最少。

这是一个比较典型的动态规划题目，比较容易想到可以令f[i][j]表示完成前i关如果总答错题目数是j次，最少需要的总答对题目数。

按关卡划分阶段，每次转移就是枚举第i关答错的题目数x，即

f[i][j] = min{f[i-1][j-x] + c[i][x], | x = 0 .. ⌈Ai/T⌉}

最后我们要在所有f[n][j]，j=0..M中找到最小的j满足f[n][j] + j <= M。

这个算法总状态数是O(NM)的，转移复杂度是O(max{Ai})的。对于极限数据还是可能超时。

另一种动态规划算法需要我们换一种状态表示。我们可以用g[i][j]表示答错i题，答对j题时，能达到的 最好记录 是什么。

这里记录用一个二元组(x, y)表示，其中x是关卡，y是得分。也就是说g[i][j]=(x, y)表示答错i题，答对j题时，最高能进行到第x关，并且得分是y。

显然任何两个记录(x1, y1)和(x2, y2)都是可比较优劣的。同时为了描述方便，我们定义一个记录"加"得分的算子+，(x1, y1) + s = (x2, y2)表示：如果当前在第x1关y1分，那么再加s分之后，到达的是第x2关y2分。

我们可以按答题总数划分阶段，每次转移就是枚举最后一题是答对还是答错了：

g[i][j] = max{g[i-1][j] + T, g[i][j-1] + S}

最后我们在所有g[i][j]里找到通过第n关，并且j最小的。

这个算法总复杂度是O(M^2)，转移是O(1)的。