1、
思路:拓撲排序,不解釋了
2、
思路:
本來以為他是一個圖論問題,找最大環。
但其實對于這種情況,他是要輸出0的,而不是9,是以他不是一個圖論問題,他帶有順序性,這種可以用dp來維護。
abc
efa
cde
dp[i][j],代表i王朝并且以j字元結尾的最大長度。
對于每一個串假設是abc,那麼要更新,并且周遊,僞代碼如下:
# 先更新自身
dp[a][c]=max(dp[a][c], 3)
# 再更新其他節點
for i in range:
dp[i][c] = max(dp[i][c], dp[i][a] + len("abc"))
注意更新的時候必須第一維的所有節點都要更新,因為都算是有用狀态!!!别隻更新dp[c][c]了。
最後周遊:
for i in range("abcde...xyz"):
ans = max(ans, dp[i][i])
ans就是答案
3、