首頁

Difficulty:

⭐️⭐️⭐️⭐️

# Problem Description 題敘:

Link

Easy Version - Link (單調對列優化)

  1. 由下而上給你 nn 隻烏龜，你可以挑選一些烏龜，把他們融合起來成一隻，如此，他們的違和度也會相加。
  2. xx 個烏龜合出的大烏龜會有強度 xx 的違和光芒。(斜率優化版才有)
  3. 一隻違和度 cc 的烏龜如果放在烏龜塔的第 mm 層 ，看起來會有 c×(m−1)c\times(m-1) 的違和度。(層 = 融合後，由下而上的數第 mm 隻烏龜)
  4. 烏龜塔的違和度是所有烏龜的違和度減掉所有違合光芒的強度。(斜率優化版才需考慮光芒)
  5. 為了避免烏龜塔太矮，每個要融合的連續區段不能包含超過 kk 隻烏龜。
  • 簡易版與困難版唯一的不同就是 "光芒的有無"。

# Thinking 思考歷程:

最直覺的方法可能像是: $dp [i][j] = $ 考慮前 ii 隻烏龜，有了 jj 個堆。不過然後呢？我們分成了 jj 個堆，每個堆都乘以違和度 ×\times 層數？好像不太好做。怎麼辦？不會了。 (跑去看題解 (又作弊

# Solution 題解:

這題真的比較難​，有滿多的門檻要跨過。光轉移就不是很好理解，題解也看了好久才有一點頭緒。我們先此題的簡單版下手，最後再把斜率優化加上去就是這題的正解。

# 狀態與轉移 💡​

這個轉移式可能不太好理解，我們慢慢來。

可以觀察一個很特別的條件。違和度是乘上第 m−1m-1 層，這意味著，若是第 11 層的話，根本不用算，因為 c×(1−1)=0c \times (1-1) = 0 。如果我們正的做 dpdp ，越往上，要乘的層數數字會越來越大... 這.... 好像有點難算。

那... 如果倒著做 (由上而下) 呢？或許會想說: 「阿 可是這樣不是只是先乘大的層數再乘小的層數，有差嗎？-_-」，其實是有差的喔，而且若倒著做，計算方式不必那麼複雜。

⟸i增加的方向，由後往前dp\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \Large\Longleftarrow i\ 增加的方向，由後往前\ dp \\

c1,c2,c3,c4\Large c_1,\ c_2,\ c_3,\ c_4

觀察到這個條件後，我們就能定義狀態: dp[i]⟹dp[i] \Longrightarrow 以 ii 為最底層，考慮前 0∼i0 \sim i 的最佳解。

之後就是轉移，我們可以得到:

dp[i]=maxdp[j]+Sum[j],for(i−k≤j≤i−1)\Large dp[i] = max\\{\ dp[j] + Sum[j]\ \\}, for\ (i-k \leq j \leq i -1)

其中， jj 的範圍的訂定是由於題目連續區段不能超過 KK 的限制。而 倒著做 dpdp 的精髓是，我們當前枚舉到的 j∼ij \sim i 隻是 最底層 的，所以轉移中我們只需要枚舉他的數量，再加上之前算過的答案。

又由於我們是從上往下 (序列的後面做到前面) 做 dpdp ，最底層那堆的違和度會 ×0\times 0 ，因此，不管烏龜多大隻或多小隻，跟本不用去考慮他的違和度。

踩在上述的特性上，每前進一個 jj ，其實就是 dp[j]dp[j] 的答案 再多一個違和度前綴和 S[j]S[j]。為甚麼？

想像一下，因為多枚舉了最底層 (第 00 層)，那原本的最底層 (第 00 層) ⟹\Longrightarrow 第 11 層，第 22 層 ⟹\Longrightarrow 第 33 層 ... 第 nn 層 ⟹\Longrightarrow 第 n+1n+1 層。層數一起都往上挪動而增加了 11 ，且每個烏龜又最多只能被融合一次，因此不管之前的分堆有多麼的複雜，都不用去理他。有點像分配律的概念，反正要求的是烏龜塔違和度 總和，所以我們只要加上一個前綴和，剛剛好。 --- Code-1

# 單調隊列優化 💡​

講完了轉移，我們再回顧一下遞迴式，我們發現，maxmax 裡面的東西只跟 jj 有關係，且每次要求 極值 (最大值)，這個是一個單調隊列使用的觀察。我們看到在 ii 一直往左走的同時，jj 會往右看，是一個有 時間性 的區間範圍。這是甚麼意思呢？在我們的區間內若有一個最大值 xx，只要我們的 xx 跟 ii 的距離超過了題目給定了 KK ，他就超過了時限，不能再是最大值了。

於是我們用 deque 維護一個單調遞減的序列，我們也能看到，如果當前新的 jj 值比當前 deque 最右端的 jj 值還大的話，那麼最右端的 jj 值就沒有用了，可以直接 pop_back() 。更進一步，若新的值實在太大，還可能一路往前砍掉許多值，直到 deque 最右端的元素比他還大，或者 deque 為空。最後再把新的 jj 值推入 deque 。

也因為這個單調性的性質，我們每次取用最大值都能用 dq.front() 在 O(1)O(1) 的時間得到，且每個值只會進、出 deque 各一次，因此我們就能把複雜從 O(n2)O(n^2) 優化到 O(n)O(n) 。 --- Code-2

# 斜率優化 💡​

重頭戲來了。剛剛單調對列的解法只能用來處理簡單版的烏龜疊疊樂，這題原本預設的解是斜率優化，比簡單版多了要扣掉光芒這個條件，因此，我們必須先改一下轉移式:

dp[i]=maxdp[j]+Sum[j]−(i−j)2,for(i−k≤j≤i−1)\large dp[i] = max\\{\ dp[j]\ + Sum[j]\ - (i-j)^2\ \\},\ for\ (i-k\leq j\leq i-1)

這樣就是我們的 O(n2)O(n^2) 的算法，直接 submit 上去顯然會 TLE. 我們想想能不能用單調對列優化... 發現好像不行耶！maxmax 裡面的東西不只有 jj ，有 (i−j)2(i-j)^2 這個鬼東西，可惡，怎麼辦？

又作一些觀察，我們先展開差的平方公式 (i−j)2(i-j)^2 ，再把只跟 ii 相關的值拿出 maxmax\\{\\}，可得到遞迴式:

dp[i]=maxdp[j]+Sum[j]+2ij−j2−i2,for(i−k≤j≤i−1)\large dp[i] = max\\{\ dp[j]\ + Sum[j]\ + 2ij - j^2\ \\} - i^2,\ for\ (i-k\leq j\leq i-1)

咦？這裡是不是有點特別的感覺？這有沒有看起來像一個直線方程式？若把 ii 當作直線方程式的 xx，有沒有像 y=ax+by = ax + b ?

若寫的更清楚一點，在 y=ax+by = ax + b 中:

a=2ia = 2i

b=dp[j]+Sum[j]−j2b = dp[j] + Sum[j] - j^2

y=dp[i]+i2y = dp[i] + i^2 ，因此 y−i2y - i^2 就是我們這次的 dpdp 值。

那 deque 裡面的元素們就會是一個函數嘛，且注意到我們的 aa 係數，他一定是遞增的喔。每加進去一條新的線，斜率又會比上一條還要更大，這是因為 ii 只會遞增，所以造成斜率也會是 單調遞增 的。這個時候，就滿足了使用 斜率優化 的條件。

為了以下為了說明的方便，我們可以拿以下三條線作比較:

$T_1: $ 倒數第二條線 (黑)

T2:T_2 : 最後一條線 (紅)

T3:T_3: 當前新的直線 (藍)

  • $NOTE: $ 以下的內容可以搭配下圖當作參考。

斜率優化跟單調對列其實還滿像的，若 在 deque 最前面的直線超過了給定的範圍 KK ，就會老死。

但有些地方不太一樣喔，我們不能像單調對列 只有做 以下的事: 「對於新的直線的 yy 值，若比 當前在 deque 裡面 最右邊的直線的 yy 值還要大的話，那麼就往前砍掉比他還小的直線 」，這樣會出問題！如果新的線無法在當時取代最後一條線，那在 T3T_3 就失去了 在之後的 ii 能提早取代 T2T_2 的機會，意即，在往後的 ii 中，T3T_3 可能已經比 T1T_1 強了，但若是 T2T_2 還沒老死，那我們的 maxmax 就會選到 T2T_2 而不是極值 T3T_3 ，這個時候就會出 BUG。要處理這個問題的話，我們可以先轉換一下，有一個很好的思維，就是 「最後再來維護 deque 的最前面要是最大值」這個特性。只要在取用 maxmax 值前，用一個 while 迴圈一直讓 dq[0] 跟 dq[1] 做 yy 值比較， 若 dq[0] 小於 dq[1] 就 popfrontpop\ front ，到最後就會是我們當前要的直線了。

另一點比較不一樣的是，儘管 T1T_1 可能在當前無法直接取代 T2T_2，然而，T3T_3 若跟 T1T_1 聯手，是有可能把前一條線給取代掉的喔。更詳細的說，再次強調 因為斜率一定是遞增的，看到交點就意味著前一個直線必定死亡，那麼，若 T3T_3 與 T2T_2 的 xx 座標交點，小於 T2T_2 與 T1T_1 的 xx 座標交點，這代表著，T2T_2 在把 T1T_1 給殺掉前，T3T_3 就已經把 T2T_2 給殺掉了。T2T_2 永遠不會有當最大值的時候， 因此可以直接把他 poppop 掉。此動作就是俗稱的 夾殺。

交點的 xx 座標公式 可以藉由一點簡單的國中數學推導出來:

\displaylines{\large y = ax + b \\\ \large y' = cx + d \\\ \\\ \large ax + b = cx + d \\\ \large ax - cx = d - b \\\ \\\ \large x = \frac{d - b}{a - c}}

交點是求出來了，但是，這樣又會出一個問題，我們若把 T2T_2 給夾殺掉了，這個意思是 我們 能完全確定 T2T_2 用不到，也就是說，我們認為 「在 T1T_1 和 T3T_3 的交點以前，T1T_1 是最佳選擇，在之後的話則是 T3T_3 是最佳選擇」，但其實「在 T1T_1 和 T3T_3 的交點以前」有可能 T1T_1 已經老死了！這個時候我們就很不幸的把以後的最佳選擇給夾殺掉了。

那為了解決這個問題，我們必須多考慮 T1T_1 會提早死亡的可能。因此，對於一條直線的預設死期，就是就是該直線加進去的 xx 座標 +K+\ K ， 我們先讓他跟 T1T_1 與 T2T_2 的 xx 座標交點取 minmin ，再跟 T2T_2 與 T3T_3 的 xx 座標交點比較，來決定是否該夾殺 T2T_2 。

** 對於每條線的死期，我們能再換另一個角度去想，若把線想成一個 線段，也許會更直觀一點 (?)

** 這題數字很大，每一個加跟乘都很容易爆 int ，因此一定要用 long long 。

# AC Code 程式碼:

# Code-1 (單調隊列版) O(n2)O(n^2)

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int oo = 2e9;
const int N = 5e5+5;
void _debug() {cerr << '\n';}
template <typename A, typename... B>
void _debug(A a, B... b) {cerr << a << ' ', _debug(b...);}
#define debug(args...) cerr << '(' << (#args) << ") : ", _debug(args)
LL sum[N] = {}, dp[N];
int main(){
    int n, k; cin>>n>>k;
    for(int i = n; i > 0; i--) cin>>sum[i]; //index 1 ~ n
    for(int i = 0; i < n; i++) sum[i+1] += sum[i];
    for(int i = 0; i<=n; i++) dp[i] = -oo;
    dp[0] = 0;
    for(int i = 1; i <= n; i++){ 
        for(int j = max(0, i-k); j < i; j++){
            dp[i] = max(dp[i], dp[j] + sum[j]);
        }
    }
    cout<<dp[n]<<'\n';
}
# Code-2 (單調隊列版) O(n)O(n)
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int oo = 2e9;
const int N = 5e5+5;
void _debug() {cerr << '\n';}
template <typename A, typename... B>
void _debug(A a, B... b) {cerr << a << ' ', _debug(b...);}
#define debug(args...) cerr << '(' << (#args) << ") : ", _debug(args)
LL sum[N] = {}, dp[N];
int main(){
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int n, k; cin>>n>>k;
    for(int i = n; i > 0; i--) cin>>sum[i]; //index 1 ~ n
    for(int i = 0; i < n; i++) sum[i+1] += sum[i];
    for(int i = 0; i<=n; i++) dp[i] = -oo;
    dp[0] = 0;
    deque<pair<LL,LL>> dq; // 大到小維護，{進來的時間，強度}
    dq.push_back({0, 0}); // 能力一定最弱的 j
    for(int i = 1; i <= n; i++){ 
        if(dq.empty()^1 && dq.front().first < i - k) dq.pop_front(); //Out of scope, 老死的
        dp[i] = dq.front().second;
        LL val = dp[i] + sum[i]; // 這次的 i，變成下一次的 j
        while(dq.empty()^1 && dq.back().second < val){
            dq.pop_back();
        }
        dq.push_back({i, val});
    }
    cout<<dp[n]<<'\n';
}
# Code-3 (斜率優化版) O(n)O(n)
#include <bits/stdc++.h>
typedef long long LL;
using namespace std;
const int N = 5e5+5;
LL sum[N] ={}, dp[N], n, k;
//dp [i] -> 以 第 i 層為最底層，考慮第 i ~ n 的最佳解
struct LINE{
    LL a,b,x; //x 就是 i. 也就是上一條線的死期
    LINE(){}
    LINE(LL _a, LL _b, LL _x): a(_a), b(_b), x(_x){}
};
int squeez(LINE l1, LINE l2, LINE l3){
    return min(l1.x + k, (LL)(l2.b - l1.b)/(l1.a - l2.a)) > (l3.b - l2.b) / (l2.a - l3.a);
}
int beat(LINE f, LINE s, LL x){ 
    return f.a*x + f.b < s.a*x + s.b;
}
int main(){
    cin>>n>>k;
    for(int i = n; i > 0; --i) cin>>sum[i];
    for(int i = 0; i < n; i++) sum[i+1] += sum[i];
    deque<LINE> dq;
    dq.emplace_back(0,0,0); // 推入一個斜率一定最小線
    for(LL i = 1; i <= n; i++){ // 由後往前，考慮前 i 隻烏龜
        if(dq.empty()^1 && dq.front().x < i - k) dq.pop_front(); // 老死。deque 裡最多只能有 K 隻烏龜。
        //pop 掉值比較小的
        while(dq.size()>=2 && beat(dq[0], dq[1], i)) dq.pop_front();
        // 計算新線        
        LL a = dq.front().a, b = dq.front().b;
        dp[i] = a*i + b - i*i;
        a = 2*i; b = dp[i] + sum[i] - i*i; // 變為下次的 max.
        LINE T3 = LINE(a,b,i);
        // 處理夾殺
        while(dq.size() >= 2 && squeez(dq[dq.size()-2], dq[dq.size()-1], T3)) dq.pop_back();
        // 推新的線進去 deque
        dq.push_back(LINE(a, b, i));
    }
    cout<<dp[n]<<'\n';
}
<br/>
# 學習到的新技巧 or 概念～
自己在之前從來沒有寫過單調隊列與斜率優化，寫起來不是很順手，但藉由這題，感覺學到了好多 XD
  • 單調對列優化初體驗
  • 斜率優化初體驗
  • 比較難的題目，可以先寫個較爛的複雜度的解法丟上去，這樣思考正解的時候比較不會迷失方向。