天天看點

2022-08-21 星環科技-C++開發筆試

 1、

2022-08-21 星環科技-C++開發筆試
2022-08-21 星環科技-C++開發筆試

 思路:拓撲排序,不解釋了

2、

2022-08-21 星環科技-C++開發筆試
2022-08-21 星環科技-C++開發筆試

思路:

本來以為他是一個圖論問題,找最大環。

但其實對于這種情況,他是要輸出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、

2022-08-21 星環科技-C++開發筆試
2022-08-21 星環科技-C++開發筆試

繼續閱讀