這題我們可以試著用 dp 來解決他,定義 dp[i] 代表選擇第 i 個元素且總共選擇個數不超過 k 的最大值
則 dp[i] = max(sum(i, j)), for all i >= j >= i - k + 1
而 sum(i, j) 代表 [j, i] 這段區間的總和,我們也可以換成前綴和的寫法,定義 s[i] 為原序列前 i 項的總和,則
dp[i] = max(s[i] - s[j - 1]), for all i >= j >= i - k + 1
但是這樣轉移太慢了,所以我們想辦法優化一下
觀察後可以發現,要求最大的 s[i] - s[j - 1] ,也就是說對於 i 來說,他一定是從符合規定且最小的 j - 1 轉移過來的,所以我們只要維護 i >= j >= i - k + 1 當中最小的 s[j - 1] 就好了。
這樣就變成滑動視窗區間最小值問題了,用 deque 維護一下即可,均攤下來時間複雜度為 O(N)
不會維護的可以參考這篇文章 https://usaco.guide/gold/sliding-window?lang=cpp
裡面有講怎麼做 Sliding Window Minimum in O(N)
這題我們可以試著用 dp 來解決他,定義 dp[i] 代表選擇第 i 個元素且總共選擇個數不超過 k 的最大值
則 dp[i] = max(sum(i, j)), for all i >= j >= i - k + 1
而 sum(i, j) 代表 [j, i] 這段區間的總和,我們也可以換成前綴和的寫法,定義 s[i] 為原序列前 i 項的總和,則
dp[i] = max(s[i] - s[j - 1]), for all i >= j >= i - k + 1
但是這樣轉移太慢了,所以我們想辦法優化一下
觀察後可以發現,要求最大的 s[i] - s[j - 1] ,也就是說對於 i 來說,他一定是從符合規定且最小的 j - 1 轉移過來的,所以我們只要維護 i >= j >= i - k + 1 當中最小的 s[j - 1] 就好了。
這樣就變成滑動視窗區間最小值問題了,用 deque 維護一下即可,均攤下來時間複雜度為 O(N)
不會維護的可以參考這篇文章 https://usaco.guide/gold/sliding-window?lang=cpp
裡面有講怎麼做 Sliding Window Minimum in O(N)
果然是daniel play minecraft