f582. 4. 病毒演化 -- 2020年7月APCS | From: [36.225.5.242] | 發表日期 : 2023-10-13 21:27

完整題解：https://moon-jam.me/zerojudge_f582/

 

解題思路：

這題我是用DP寫，並使用DFS從根遍歷整棵樹，在過程完成狀態轉移。

在寫這題的時候，最困難的應該就是要想怎麼定義狀態還有狀態轉移如何在O(1)內做出來，而首先按照題目可知，不同位置的字元，無論在哪個點都不受影響，而當該點的某個位置為@時，其有機會是A、U、C、G任意一個，因此不妨定義dp[i][j][k]代表第i個陣列的第j個字元為k時的單點至葉子最小距離(A, U, C, G分別對應到k = 1, 2, 3, 4)，而當第i個陣列的第j個字元已經被定義時(也就是不為@時)就將其餘的點設為極大值，而在狀態轉移時，就會是他各個小孩在四種狀態的值加上與他的距離(就是看小孩當前狀態是否跟父母一樣，一樣距離就是0不一樣就是1)的最小值，以數學式表達如下：(其中child代表第i個陣列的小孩個數，child_p代表第i個陣列第p的小孩)

dp[i][j][k] = \sum_{p=1}^{child} min(dp[child_p][j][1] + (k != 1), dp[child_p][j][2] + (k != 2), dp[child_p][j][3] + (k != 3), dp[child_p][j][4] + (k != 4))

而最後答案就是：

\sum_{j=0}^{m-1} min(dp[root][j][1], dp[root][j][2], dp[root][j][3], dp[root][j][4])

總複雜度為O(nm)

🌟 在當沒有小孩時(葉子)，其各點的dp除設為極大值的位置外，均為0。