CF1566F (動态規劃)

題目大意：

n ( ≤ 2 e 5 ) n(\le 2e5) n(≤2e5)個數軸上的點， m ( ≤ 2 e 5 ) m(\le 2e5) m(≤2e5)個數軸上的線段。每一次可以移動任意一個點移動機關一的距離

最少操作多少次可以使的每個線段至少被一個點通路過

解題思路：

• 對于本身覆寫了點的線段可以删除掉
• 對于大的線段覆寫了小的線段，大的線段可以删除掉，因為要周遊到小線段，則必然會經過大線段，是以可以删除
• 對于兩個點之間的線段，顯然是由這兩點來通路是最優的

• 設 d p [ i ] [ k ] dp[i][k] dp[i][k]為第 i i i個點通路右邊 k k k個線段的最小值，有 d p dp dp方程：

  d p [ i ] [ k ] = m i n ( d p [ i − 1 ] [ j ] + 2 ∗ m i n ( a [ i ] − r i − 1 [ j + 1 ] , l i [ k ] − a [ i ] ) + m a x ( a [ i ] − r i − 1 [ j + 1 ] , l i [ k ] − a [ i ] ) ) 因 為 要 對 于 第 i 個 點 ， 如 果 要 訪 問 兩 邊 的 線 段 ， 必 然 會 存 在 先 訪 問 右 邊 還 是 先 訪 問 左 邊 的 問 題 ， 而 顯 然 是 先 訪 問 小 的 距 離 先 通 過 以 上 d p 方 程 ， 時 間 複 雜 度 似 乎 是 O ( n 2 ) 的 但 是 可 以 發 現 ， 如 果 a [ i ] − r i − 1 [ j + 1 ] 以 及 l i [ k ] − a [ i ] 都 随 j ， k 單 調 的 所 以 可 以 用 雙 指 針 以 及 m u l t s e t 優 化 且 d p 方 程 可 以 變 形 為 如 下 方 程 ： d p [ i ] [ k ] = m i n ( d p [ i − 1 ] [ j ] + l i [ k ] − r i − 1 [ j + 1 ] + m i n ( a [ i ] − r i − 1 [ j + 1 ] , l i [ k ] − a [ i ] ) ) dp[i][k]=min(dp[i - 1][j] + 2 * min(a[i] - r_{i-1}[j + 1], l_i[k]-a[i])+max(a[i] - r_{i-1}[j + 1], l_i[k]-a[i])) \\ 因為要對于第i個點，如果要通路兩邊的線段，必然會存在先通路右邊還是先通路左邊的問題，而顯然是先通路小的距離先 \\ 通過以上dp方程，時間複雜度似乎是O(n^2)的 \\ 但是可以發現，如果a[i]-r_{i-1}[j+1]以及l_i[k]-a[i]都随j，k單調的是以可以用雙指針以及multset優化 \\ 且dp方程可以變形為如下方程： \\ dp[i][k]=min(dp[i-1][j]+l_i[k]-r_{i-1}[j+1]+min(a[i] - r_{i-1}[j + 1], l_i[k]-a[i])) dp[i][k]=min(dp[i−1][j]+2∗min(a[i]−ri−1​[j+1],li​[k]−a[i])+max(a[i]−ri−1​[j+1],li​[k]−a[i]))因為要對于第i個點，如果要通路兩邊的線段，必然會存在先通路右邊還是先通路左邊的問題，而顯然是先通路小的距離先通過以上dp方程，時間複雜度似乎是O(n2)的但是可以發現，如果a[i]−ri−1​[j+1]以及li​[k]−a[i]都随j，k單調的是以可以用雙指針以及multset優化且dp方程可以變形為如下方程：dp[i][k]=min(dp[i−1][j]+li​[k]−ri−1​[j+1]+min(a[i]−ri−1​[j+1],li​[k]−a[i]))

• 想的時候想起來覺得挺複雜的，但是寫起來隻要明了了就還好

AC代碼：

#include <bits/stdc++.h>
#define ft first
#define sd second
#define pb push_back
#define IOS ios::sync_with_stdio(false), cin.tie(0), cout.tie(0) //不能跟puts混用
#define seteps(N) fixed << setprecision(N)
#define endl "\n"
const int maxn = 2e5 + 10;
using namespace std;
typedef long long ll;
typedef double db;
typedef pair<int, int> pii;
const ll inf = 2e15 + 7;
int t, n, m, cnts;
ll a[maxn];
pii seg[maxn], tseg[maxn];
vector <int> len[maxn]; //分段,len[i]中的線段全在i-1~i号點範圍内
ll dp[2][maxn], lp[maxn], rp[maxn], ln[maxn], rn[maxn];
multiset <ll> s;
void init0() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++) cin >> a[i];
    for (int i = 1; i <= m; i++) cin >> seg[i].ft >> seg[i].sd;
    sort (a + 1, a + n + 1);
    sort (seg + 1, seg + m + 1);
    /* 初始化 */
    a[0] = -inf;
    cnts = 0;
    for (int i = 1; i <= max(n, m) + 1; i++) len[i].clear(), dp[0][i] = dp[1][i] = inf;
    dp[0][0] = dp[0][1] = inf;
    
}
void init1() {
    /*這部分先将已經有點在裡面的删除掉*/
    int p = 1, i = 1, j;
    a[n + 1] = 1e9 + 10;
    while (i <= m) {
        if (seg[i].ft <= a[p] && a[p] <= seg[i].sd) i++;
        else if (a[p] < seg[i].ft) p++;        
        else tseg[++cnts] = seg[i], i++;
    }
    for (int i = 1; i <= cnts; i++) seg[i] = tseg[i];
    m = cnts;
    /*這部分将那些大的包含小的，大段删除掉，保留小的*/
    cnts = 1;
    for (int i = 2; i <= m; i++) {
    //    seg[cnts].sd = seg[i].sd;
        if (seg[cnts].sd < seg[i].sd) seg[++cnts] = seg[i];        
        else {
            while (seg[cnts].sd >= seg[i].sd && cnts > 0) cnts--;
            seg[++cnts] = seg[i];
        }
    }

    m = cnts;

    /* 分段 */
    for (i = 1, j = 1; i <= n; i++) {
        for (; j <= m; j++) {
            if (seg[j].sd < a[i]) 
                len[i].pb(j);
            else break;
        }
    }
    while (j <= m) len[n + 1].pb(j++);
}
void init2() {
    int p = 0, id;
    ll res = 0;
    if (len[1].empty()) { //前面為空
        dp[1][0] = 0;
        for (int i = 0; i < len[2].size(); i++) dp[1][i + 1] = seg[len[2][i]].ft - a[1];
    }
    else {
        for (int i = 0; i < len[1].size(); i++) {
            p = len[1][i];
            if (res < a[1] - seg[p].sd) id = p, res = a[1] - seg[p].sd;
        }
        len[1].clear();
        len[1].pb(id);  
        for (int i = 0; i < len[2].size(); i++) {
            p = len[2][i];
            if (seg[p].ft - a[1] > a[1] - seg[id].sd) dp[1][i + 1] = 2 * (a[1] - seg[id].sd) + seg[p].ft - a[1];
            else dp[1][i + 1] = 2 * (seg[p].ft - a[1]) + a[1] - seg[id].sd;
        }
        dp[1][0] = a[1] - seg[id].sd;        
    }
    return;

}
void solve() {
    for (int i = 2; i <= n; i++) {
        int p1 = 0, p2 = len[i + 1].size();
        int pre = (i - 1) & 1, now = i & 1;
        int num1 = len[i].size(), num2 = len[i + 1].size();
        /*start:為了友善将點之間線段存到另一個數組裡*/
        for (int j = 1; j <= num1; j++) lp[j] = seg[len[i][j - 1]].ft, rp[j] = seg[len[i][j - 1]].sd;
        lp[0] = rp[0] = a[i - 1];
        lp[num1 + 1] = rp[num1 + 1] = a[i];

        for (int j = 1; j <= num2; j++) ln[j] = seg[len[i + 1][j - 1]].ft, rn[j] = seg[len[i + 1][j - 1]].sd;
        ln[0] = rn[0] = a[i];
        ll mmin = inf;
        /*end*/

        /*start:将值存入multiset中*/
        s.clear();
        for (int j = 0; j <= num1; j++) s.insert(dp[pre][j] - 2 * rp[j + 1] + a[i]);
        int test = s.size();
        /*end*/
        while (p1 <= num1 && p2 >= 0) {
            while (ln[p2] - a[i] <= a[i] - rp[p1 + 1] && p1 <= num1) {
                mmin = min(mmin, dp[pre][p1] - rp[p1 + 1]);
                s.erase(s.find(dp[pre][p1] - 2 * rp[p1 + 1] + a[i]));
                p1++;
            }
            if (!s.empty()) dp[now][p2] = min(mmin + ln[p2] - a[i], (*s.begin())) + ln[p2];
            else dp[now][p2] = mmin + 2 * ln[p2] - a[i];
            p2--;
        }
        while (p2 >= 0) dp[now][p2] = mmin + ln[p2] - a[i] + ln[p2], p2--; 
    }
}
int main() {
    cin >> t;
    while (t--) {
        init0(); //輸入并進行整個數組的初始化
        init1(); //将某些無用的線段去除掉并進行分段
        init2(); //預處理開頭的點
        solve();
        cout << max(dp[n & 1][len[n + 1].size()], 0ll) << endl;
    }
    
    return 0;
}