#36625: 解題想法
frankleeplayminecraft58@gmail.
...
(LJH-code)
學校
:
高雄市立前鎮高級中學
編號 : 119456
來源 : [140.114.216.100]
最後登入時間 ：
2024-03-24 11:15:22
可以朝 dp 的方向去想，令 dp[i][l][r] 代表在中序區間 [l, r] 中以 i 為根結點去構造出一棵樹的最大分數
那轉移就是 dp[i][l][r] = max(dp[j][l][i - 1] * dp[k][i + 1][r] + a[i]), j \in [l, i), k \in (i, r]
記得考慮 basecase 跟 左/右子樹為空的情況
回朔的部分就是用 dp 紀錄的答案去回朔就好，但是可能有多組解，請輸出字典序最小的那個
#36632: Re: 解題想法
可以朝 dp 的方向去想，令 dp[i][l][r] 代表在中序區間 [l, r] 中以 i 為根結點去構造出一棵樹的最大分數
那轉移就是 dp[i][l][r] = max(dp[j][l][i - 1] * dp[k][i + 1][r] + a[i]), j \in [l, i), k \in (i, r]
記得考慮 basecase 跟 左/右子樹為空的情況
回朔的部分就是用 dp 紀錄的答案去回朔就好，但是可能有多組解，請輸出字典序最小的那個
不愧是 daniel
#36633: Re: 解題想法
frankleeplayminecraft58@gmail.
...
(LJH-code)
學校
:
高雄市立前鎮高級中學
編號 : 119456
來源 : [140.114.216.100]
最後登入時間 ：
2024-03-24 11:15:22
可以朝 dp 的方向去想，令 dp[i][l][r] 代表在中序區間 [l, r] 中以 i 為根結點去構造出一棵樹的最大分數
那轉移就是 dp[i][l][r] = max(dp[j][l][i - 1] * dp[k][i + 1][r] + a[i]), j \in [l, i), k \in (i, r]
記得考慮 basecase 跟 左/右子樹為空的情況
回朔的部分就是用 dp 紀錄的答案去回朔就好，但是可能有多組解，請輸出字典序最小的那個
不愧是 daniel
daniel07 你真的太諧了
ZeroJudge Forum