抄了某位大大的code之後
稍微修改一下後 發現其實程式碼超短的
![]()
題目 [我覺得有dp成分 但tag沒有]
題目敘述非常簡單
可以想像是在字串中計算呈現 abab 的子序列
(a = b) 的話 也算 (也就是4個都相同)
最暴力的就是 Cn取4
但這樣複雜度是 O(n⁴ / 120)
但其實能夠降到O(n²) (還能更快嗎?)
------------------------------
以下進入詳解
首先
這個題目其實等同於
在陣列中計算有幾對相同的pair
(對中的index不可重複, 兩個pair的位置不能交叉)
但我覺得這跟我要講的解法
想法上沒有什麼太大的關係
只是稍微提一下 (tutorial也有講到)
先上程式碼
- ans = 0
- count = [0] * 3007
- for i in range(n):
- c = 0
- for j in range(i + 1, n):
- if arr[i] == arr[j]:
- ans += c
- c += count[arr[j]]
- count[arr[i]] += 1
沒錯 扣掉一些IO的部分 就是那麼短
(而且我後來又改的很ppyy)
我們開個陣列 (也可用 map/dict)
count 用來記錄各個數字出現的次數
我們以 前綴/累加 的方式計算
負責統計之前出現的數字的次數
可以讓我們快速地做查詢 第一個 位置
而 arr[i] 代表 第二個
也就是說我們枚舉陣列中的每個數字當作是 第二個
之後我們宣告一個變數 c
下一層 迭代每個數字 arr[j] 當作是 第三個
然後回去找前面有幾個數字可以當 第一個
也就是在 count 裡面的值，然後加進 c
同時也順便把這 第三個 數看作是 第四個
如果這 第四個 數字符合 (也就是他跟 第二個 數字一樣)
這時 c 的值就會被加進 ans
可以再仔細思考一下計算的正確性
------------------------------
過一陣子回去看 再來寫詳解
發現其實概念也沒有到很難
只是要想出這種優美的 dp 手法
在賽中確認可行性 並在短時間喇出來
還得再多多努力
不知道我這樣有沒有講清楚
有可能之後再回去看的時候 會再修
歡迎大家留言指教
創作內容
cf Edu#94 (Div. 2) pD Zigzags
未分類 (17)