Python60分超时求助

P1005 [NOIP2007 提高组] 矩阵取数游戏

@[X_7a](/user/685861) `fun`中有个`ij.index((i,j))`,这个东西反复使用会花费大量的时间,建议把`zhi`换成二维数组(列表套列表也行),初始化全为$0$,然后用`zhi[i][j]==0`判断有没有计算过即可。 用`OI`人的话说,这个`index`的复杂度是约为$O(n^{2})$的,其余部分的复杂度在$O(mn^{2})$,所以整体复杂度在$O(n^{4}m)$,基本直接超时。再加上`python`本身运行效率不高,`TLE`是正常现象
by Wangzj512 @ 2023-06-22 12:26:04


一种初始化方法: `zhi=[[0]*85]*85`
by Wangzj512 @ 2023-06-22 12:28:24


感谢,已经通过了,第一道蓝题(绿题都还没过)。没仔细学过时间复杂度,以为内建函数都是比较快的
by X_7a @ 2023-06-22 21:54:15


|