hiho一下第145周《智力竞赛》题目分析

15
5

《智力竞赛》题目分析

首先我们可以发现,由于每一关需要的分数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)的。

5 answer(s)

3

strong text*emphasized text*

0

感谢指点

2

感觉很多人忽略了i+j<=M这点。。。

0

有人拿Python过了吗……O(M^2)的算法一直TLE T <= 100, M <= 1000的话大概是10^8次?感觉Python一秒钟能做的事情也就10^6量级……

所以能不能把Python的时限放得更宽一点,或者在题目设计时能更巧妙地保证Python最佳算法能过,同时又不至于让C++的暴力程序AC?

如果不能的话,干脆取消Python的支持行么,允许让用Python做题却又潜在有超时的坑太难受了。(或者学SPOJ支持一下CPython或PyPy?)

  • 附一下同样算法代码的情况(我自己写的C++和Python程序): 100 / 100 智力竞赛 AC G++ 165ms 0MB 40 / 100 智力竞赛 TLE Python2 9193ms 6MB

  • 100 / 100 智力竞赛 AC Python2 1504ms 6MB 3秒前 查看<---并没有问题

  • 100 / 100 智力竞赛 AC Python2 5591ms 6MB <---好吧我做了点常数优化也过了…………不过C++直接啥都不优化暴力O(M^2)就能过,Python却要注意常数也是惨

  • 添加评论
  • reply
0

很厉害的解法!

write answer 切换为英文 切换为中文


转发分享