#31651: [解題報告] Python 遞迴法(lru_cache)


seer852741@gmail.com (St418)

School : 國立中央大學
ID : 170226
IP address : [1.171.104.23]
Last Login :
2022-09-22 22:52:33
c463. apcs 樹狀圖分析 (Tree Analyses) -- apcs | From: [220.129.100.13] | Post Date : 2022-08-12 15:08

from functools import lru_cache

@lru_cache(maxsize=None)
def getHeight(index):
    child = nodeChild[index]
    if child:
        return max(getHeight(x-1) for x in child) + 1
    else:
        return 0

n = int(input())
nodeChild = tuple(tuple(map(int, input().split()[1:])) for _ in range(n))
nodeHight = tuple(map(getHeight, range(n)))
print(nodeHight.index(max(nodeHight)) + 1)
print(sum(nodeHight))
@lru_cache(maxsize=None)
python內建的緩存功能
不加的情況下40% 加了之後70%
 
from sys import setrecursionlimit
setrecursionlimit(1000000)
修改python遞迴深度限制後95%

#19: 5% RE (SIGSEGV)

記憶體區段錯誤!
Segmentation fault (core dumped)

總結來說python不適合做遞迴
但我覺得APCS應該不會出那麼誇張的側資
用緩存裝飾子後應該就能過了(個人猜測)
 
ZeroJudge Forum