NOIP2010提高组解题报告——Tortoise

【题目大意】

给定N(1<=N<=350)个排在一行的格子,每个格子上都有一个权值。同时给出M(1<=M<=120)张卡片,每张卡片上有[1,4]中的一个数字。一开始游戏者站在第一个格子处,每使用一张写着数字x的卡片,那么向后跳x步,并得到该格子上的权值。卡片不可重复使用。数据保证每种卡片的数量不超过40,并且所有卡片上的数字之和与N-1相等。

【算法分析】

本题很容易使用动态规划解决,而且可以通过所有数据的状态定义也有很多种。由于转移都比较简单,并且几乎都一样思路,所以转移方程在此略去。

【算法一】

F[i][j][k][l]表示写着数字1、2、3、4的卡片分别剩下i、j、k、l张时的最大得分。

(可以使用n-(i*1+j*2+k*3+l*4)来得知当前到达哪一个格子)

【时间复杂度】

O(41^4+N+M)

【空间复杂度】

O(41^4+N+M)

【算法二】

F[i][j][k][l]表示跳到了第i个格子,写着数字2、3、4的卡片分别剩下j、k、l张时的最大得分。

(可以使用n-i-j*2-k*3-l*4来得知1号牌剩下多少张)

【时间复杂度】

O(N*41^3+N+M)

【空间复杂度】

O(N*41^3+N+M)

【算法三】

F[i][j][k][l]表示剩下i张牌可用,写着数字2、3、4的卡片分别剩下j、k、l张时的最大得分。

(可以使用i-j-k-l得知1号牌剩下多少张)

【时间复杂度】

O(M*41^3+N+M)

【空间复杂度】

O(M*41^3+N+M)

留下评论

您的电子邮箱地址不会被公开。