juanjuan


1. 步道規劃

Zerojudge s223


題敘

將 $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$


思路

看到 最小值 ，我們應該想到 二分搜。

我們可以 對答案二分搜，也就是對於 $x$ ，我們判斷是否存在一種合法取法使得 $每條步道總難度最大值的最小值 \ge x$。

這是可以做到的，我們可以算某段連續的和，在不超過 $x$ 的前提下，持續增加陣列長度，若會超過則代表又多了一條步道，最後再檢查 $步道數 \leq k$ 是否成立。

可能有疑問 $< k$ 為什麼可行? 實質上，因為前面取的皆不超過 $x$ ，因此若我們再把前面的拆成兩條、甚至多條也會符合，所以也可以分成 $k$ 條。

因此先對 $d$ 排序並預處理 $C$，再銜接上述的步驟，就可以了。

Time : $O(n \log n + n \log w)$，其中 $w = \sum C_{i}$。


Code :

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

#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 = c[i];
            if (nw > x) return false; 
        } else {
            nw += c[i];
        }
    }
    return (cnt <= k);
}

signed main() {
    ios::sync_with_stdio(0); cin.tie(0);
    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(0LL, 2 * (arr[i].S - arr[i - 1].S));

    int ans = 0, 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;
    return(0);
}


2. 骨牌堆疊

Zerojudge s224


題敘

有 $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$


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


思路

我們可以注意到非常特別的條件 : $a_{i}$ 不相同、 $b_{i}$ 不相同。

事實上，用肉眼觀察到可以直接分成以下二種 case，分別是 鍊狀、環狀。

image

在 case 1，直接做 Kadane’s 就可以。

在 case 2，會發現做 kadane’s 會少掉跨過銜接處的。

舉例來說是 $[1,-3,2]$ 很明顯取 $[1,2]$ 最優，但是卻無法被選取，

我們可以發現構成最優的有兩種情況 : 無跨過起點、有跨過起點，

前者是會被取到；後者則不會，因此可以記錄最小的連續陣列和，用總和扣除便是後者的狀況。

而最小的連續陣列和的思路基本跟最大的差不多。

Time : $O(m + n)$


Code :

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

#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


題敘

有 $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$


思路

我們需要考慮的狀態 : 兩個人分別做到哪，因此我們的狀態設為 : $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);
}