### 2026.3 高級

> juanjuan

#### 1. 步道規劃
[Zerojudge s223](https://zerojudge.tw/ShowProblem?problemid=s223)

:::info
題敘
將 $n$ 個觀景台分成恰 $k$ 條步道，規則如下
1. 將步道按照水平座標 $d_{i}$ 排序
2. 每條步道之中，觀景台必須連續，且至少要有一個觀景台

對於一條步道之中，兩個相鄰的觀景台 $P_{i}$、$P_{i+1}$，定義行走該段路程的體力值 $C_{i} = (d_{i+1} - d_{i}) + max(2\cdot (h_{i+1} - h_{i}),0)$ 。對於一條步道的總難度，即為該步道內所有路段體力值的總和。
輸出在所有可能步道取法之中，每條步道總難度最大值的最小值。

$1 \leq k \leq n \leq 10^5$
$1\leq d_{i},h_{i} \leq 10^9$

:::

:::warning
思路
看到 **最小值** ，我們應該想到 **二分搜**。
我們可以 **對答案二分搜**，也就是對於 $x$ ，我們判斷是否存在一種合法取法使得 $每條步道總難度最大值的最小值 \ge x$。
這是可以做到的，我們可以算某段連續的和，在不超過 $x$ 的前提下，持續增加陣列長度，若會超過則代表又多了一條步道，最後再檢查 $步道數 \leq k$ 是否成立。有些人可能會問 $< k$ 為什麼可行? 實質上，因為前面取的皆不超過 $x$ ，因此若我們再把前面的拆成兩條、甚至多條也會符合，所以也可以分成 $k$ 條。
因此先對 $d$ 排序並預處理 $C$，再銜接上述的步驟，就可以了。
Time : $O(n \lg n + n \lg w)$，$w = \sum C_{i}$

:::

實作上，我將 $d$ 、 $f$ 用 pair 存在 $arr$ 中，排序較為方便。

code

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define p pair<int,int>
#define F first
#define S second

int n,k;
vector<int>c;

bool check(int x){
    int cnt = 1,nw = 0;
    for(int i=0;i<n-1;i++){
        if(nw + c[i] > x){
            cnt++;
            nw = 0;
        }else{
            nw += c[i];
        }
    }
    return(cnt <= k);
}

signed main(){
    cin>>n>>k;
    vector<p>arr(n);
    for(int i=0;i<n;i++) cin>>arr[i].F;
    for(int i=0;i<n;i++) cin>>arr[i].S;
    sort(arr.begin(),arr.end());
    c.resize(n-1);
    for(int i=1;i<n;i++)
        c[i-1] = arr[i].F-arr[i-1].F + max((long long)0,2*(arr[i].S-arr[i-1].S));

    int ans,l = 0,r = 0,m;
    for(int i:c) r+=i;
    while(l<=r){
        m = (l+r)/2;
        if(check(m)){
            ans = m;
            r = m-1;
        }else{
            l = m+1;
        }
    }
    cout<<ans;
}

#### 2. 骨牌堆疊

[Zerojudge s224](https://zerojudge.tw/ShowProblem?problemid=s224)

:::info
題敘
有 $m$ 條張骨牌，以 $(a_{i},b_{i},w_{i})$ 表示 ，代表 $a_{i} \rightarrow b_{i}$、權重為 $w_{i}$。
若一張骨牌的後端點與另一張骨牌的前端點相同，則這兩張骨牌可以接在一起。
請找出一條合法的骨牌序列，使得所有權重和最大，並輸出。
保證所有的 $a_{i}$ 不相同、 $b_{i}$ 不相同。

$1\leq n \leq 4\cdot 10^5$、$1\leq m \leq 3\cdot 10^5$、$m \leq n$
$1\leq a_{i},b_{i} \leq n$、$-1000 \leq w_{i} \leq 1000$
:::

:::spoiler 先備知識 : Kadane's Algorithm
用來求最大子陣列和。
本質是 DP ，但也有一派說法是 Greedy。
令 $dp[i]$ 表以當前為結尾的最大子陣列和(可以為空陣列)，顯而易見會有$dp[i] = max(dp[i-1] + num[i],0)$。
那就依此想法繼續優化，因為轉移只會用到前一項，所以我們多開一個變數紀錄 $dp[i-1]$，就可以把 $dp$ 陣列刪除。

Time : $O(n)$
:::

:::warning
思路
我們可以注意到非常特別的條件 : <font color="#f00">$a_{i}$ 不相同、 $b_{i}$ 不相同</font>，事實上，用肉眼觀察到可以直接分成以下二種 case，分別是 鍊狀、環狀。

在 case 1，直接做 Kadane's 就可以。
在 case 2，會發現做 kadane's 會少掉跨過銜接處的，舉例來說是 $[1,-3,2]$ 很明顯取 $[1,2]$ 最優，但是卻無法被選取，我們可以發現構成最優的有兩種情況 : 無跨過起點、有跨過起點，前者是會被取到；後者則不會，因此可以記錄最小的連續陣列和，用總和扣除便是後者的狀況。而最小的連續陣列和的思路基本跟最大的差不多。

Time : $O(m + n)$
:::

實作上，從入度為 0 的開始處理，也就是 case 1；再處理 case 2，一個小技巧是不要先將起點標記為已走過，就會自然處理到繞回環的那段。

code:

#include<bits/stdc++.h>
using namespace std;

#define p pair<int,int>
#define F first
#define S second
#define mp(a,b) make_pair(a,b)

int main(){
    int n,m,ans = -INT_MAX;
    cin>>n>>m;
    vector<p>g(n,{-1,-1});
    vector<bool>vis(n,false);
    vector<int>indeg(n,0);

    int v,u,w;
    for(int i=0;i<m;i++){
        cin>>v>>u>>w;
        v--; u--;
        g[v] = {u,w};
        indeg[u]++;
    }

    for(int i=0;i<n;i++){
        if(indeg[i] > 0) continue;
        
        v = i;
        vis[v] = true;
        
        int nw = 0;
        while(g[v]!=mp(-1,-1)){
            u = g[v].F; w = g[v].S;
            nw += w;
            ans = max(nw,ans);
            nw = max(nw,0);
            vis[u] = true;

            v = u;
        }
    }

    for(int i=0;i<n;i++){
        if(vis[i]) continue;
        int total = 0,mini = 0,nwmini = 0,nwmaxi = 0;
        v = i;
        while(vis[g[v].F]==false){
            u = g[v].F; w = g[v].S;
            
            total += w;            
            nwmini += w;
            mini = min(nwmini,mini);
            nwmini = min(nwmini,0);

            nwmaxi += w;
            ans = max(nwmaxi,ans);
            nwmaxi = max(nwmaxi,0);
            vis[u] = true;
            v = u;
        }
        
        ans = max(total - mini,ans);
    }
    cout<<ans;
    return(0);
}

#### 3. 貨物運送

[Zerojudge s225](https://zerojudge.tw/ShowProblem?problemid=s225)

:::info
題敘
有 $n$ 個地點及 $k$ 個外送任務，所有任務必須嚴格按照順序完成。
現在有 A,B 兩位外送員都在位置 1，對於每個任務 $p[i]$，你必須指派給其中一個外送員去完成。而從地點 $v$ 移動到 $u$ 的代價是 $cost[v][u]$，且當所有任務完成後都必須回到位置 n。輸出最少總花費。

$2 \leq n \leq 2000$,$1 \leq k \leq n$
$1\leq p[i] \leq n$、$0\leq cost[i][j] \leq 50$
:::

:::warning
思路
我們需要考慮的狀態 : 兩個人分別做到哪，因此我們的狀態設為 : $dp[i][j]$ 代表 A 外送員做到 $i$、B 外送員做到 $j$ 時的最小總花費，類似雙指針的思路。
因為要按照順序做，所以下一個做的任務一定是 $max(i,j)+1$，然後有兩種不同的分法，分別是給 A 做或 B 做，會有 $dp[i][x] = min(dp[i][j] + cost[p[j]][p[x]] , dp[i][x])$、$dp[x][j] = min(dp[i][j] + cost[p[i]][p[x]] , dp[x][j])$ , $x = max(i,j)+1$，然後初始狀態所有都是 $INF$，除了 $dp[0][0] = 0$。
另外，應該可以發現其實會重複算到，例如 $dp[i][j] = dp[j][i]$，所以可以在我的作法做優化，但沒有實質必要找自己麻煩。
:::

Time : $O(k^2)$

#include<bits/stdc++.h>
using namespace std;

#define INF 1e9

signed main(){
    int n,k;
    cin>>n>>k;
    vector<int>p(k+1);
    p[0] = 0;
    for(int i=1;i<=k;i++){
        cin>>p[i];
        p[i]--;
    }

    vector<vector<int>>cost(n,vector<int>(n)),dp(k+1,vector<int>(k+1,INF));
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            cin>>cost[i][j];
        }
    }
    dp[0][0] = 0;
    for(int i=0;i<k;i++){
        for(int j=0;j<k;j++){
            if(dp[i][j]==INF) continue;
            int x = max(i,j)+1;
            dp[i][x] = min(dp[i][j] + cost[p[j]][p[x]] , dp[i][x]);
            dp[x][j] = min(dp[i][j] + cost[p[i]][p[x]] , dp[x][j]);
        }
    }
    int ans = INF;
    for(int i=0;i<=k;i++){
        if(dp[k][i]==INF) continue;
        ans = min(dp[k][i] + cost[p[i]][n-1] + cost[p[k]][n-1], ans);
    }
    cout<<ans;
    return(0);
}