TIOJ 2213：花枝遊戲

TIOJ 2213：花枝遊戲

題目大意：有 $n$ 個人，戰力值為 $a_1\sim a_n$，每次可以將場上的人分成左邊和右邊，左右的人要互相戰鬥，假設左邊人的編號是 $l\sim k$，右邊的是 $k+1\sim r$，那精彩度會是 $\sum_{i = l}^{k}\sum_{j = k+1}^{r}a_ia_j$，對決完後其中一邊會被淘汰掉，剩下的人繼續對決直到剩一個人。另外會有 $m$ 個指定的對決 $u,v$，代表在過程中 $u,v$ 一定要對決到，問精彩度總和最大值。

解法：每次對決會少掉一個區間，這個區間裡的人不會對決到，並且會跟區間外所有人對決到，所以令 $pre_i$ 為 $\sum_{j = 1}^{i}a_j$，假設這個區間是 $(l,r]$，那精彩度可以表示成 $(pre_n - (pre_r-pre_l))\times (pre_r - pre_l)$。如果想讓兩個人對決到，那他們一定不能在同一個區間，且最後要留一個人，代表一定要有一個區間長度為 $1$，所以可以列出 $dp$ 式：令 $mx_i$ 為 $i$ 轉移點的左界，$dp_{i,0}$ 和 $dp_{i,1}$ 代表尚未有長度為 $1$ 之區間和已經有了，那 $dp_{i,0} = \text{MAX}_{\ mx_i≤j<i}(dp_{j,0} + (pre_n - (pre_i - pre_j))\times (pre_i - pre_j))$， $dp_{i,1} = \text{MAX}_{\ mx_i≤j<i}(dp_{j,1} + (pre_n - (pre_i - pre_j))\times (pre_i - pre_j))$，$dp_{i,1} = max (dp_{i,1}, dp_{i-1,0} + (pre_n - (pre_i - pre_{i-1}))\times (pre_i - pre_{i-1}))$。前兩個式子可以變成 $(m_jx_i+k_j)+c_i$ 的形式，也就是可以斜率優化，可以寫成 $dp_i = \text{MAX}_{\ mx_i≤j<i}(pre_j\times (2\times pre_i - pre_n) + dp_j - pre_j^2) + (pre_n - pre_i)\times pre_i$。斜率查詢不單調，且有轉移範圍，前者可以使用李超線段樹解決，後者可以用線段樹套李超線段樹。這題也有相似的技巧。

$\text{Code：}$

#pragma GCC optimize("O3")
#include <bits/stdc++.h>
using namespace std;

#define int long long
#define Waimai ios::sync_with_stdio(false),cin.tie(0)
#define FOR(x,a,b) for(int x=a;x<=b;x++)
#define pb emplace_back
#define F first
#define S second

#define lpos pos*2
#define rpos pos*2+1

const int SIZE = 6e4 + 5;
const int INF = 1e18;
const int MAX = 1e9;

struct Line {
    int m, k;
    Line() {}
    Line (int m, int k) : m (m), k (k) {}
    int operator () (const int &x) const {
        return m * x + k;
    }
};

struct Node {
    int ls, rs;
    Line line;
    Node() {}
    Node (Line line) : ls (0), rs (0), line (line) {}
} node[16 * SIZE][2];

int cnt[2], root[4 * SIZE][2];

int newnode (Line line, bool b) {
    node[++cnt[b]][b] = Node (line);
    return cnt[b];
}

void Insert (int &pos, int l, int r, Line line, bool b) {
    if (!pos) {
        pos = newnode (line, b);
        return;
    }
    auto &nd = node[pos][b];
    if (l == r) {
        if (line (l) > nd.line (l)) nd.line = line;
        return;
    }
    int mid = l + (r - l) / 2;
    if (line (mid) > nd.line (mid)) swap (line, nd.line);
    if (line.m < nd.line.m) Insert (nd.ls, l, mid, line, b);
    else Insert (nd.rs, mid + 1, r, line, b);
}

int Query (int pos, int l, int r, int x, bool b) {
    if (!pos) return -INF;
    auto &nd = node[pos][b];
    if (l == r) return nd.line (x);
    int mid = l + (r - l) / 2;
    return max (nd.line (x), x <= mid ? Query (nd.ls, l, mid, x, b) : Query (nd.rs, mid + 1, r, x, b));
}

void build (int pos, int l, int r) {
    root[pos][0] = root[pos][1] = 0;
    if (l < r) {
        int mid = (l + r) / 2;
        build (lpos, l, mid);
        build (rpos, mid + 1, r);
    }
}

void update (int pos, int l, int r, int p, Line line, bool b) {
    Insert (root[pos][b], -MAX, MAX, line, b);
    if (l == r) return;
    int mid = (l + r) / 2;
    if (p <= mid) update (lpos, l, mid, p, line, b);
    else update (rpos, mid + 1, r, p, line, b);
}

int query (int pos, int l, int r, int L, int R, int x, bool b) {
    if (l == L && r == R) return Query (root[pos][b], -MAX, MAX, x, b);
    int mid = (L + R) / 2;
    if (r <= mid) return query (lpos, l, r, L, mid, x, b);
    if (l > mid) return query (rpos, l, r, mid + 1, R, x, b);
    return max (query (lpos, l, mid, L, mid, x, b), query (rpos, mid + 1, r, mid + 1, R, x, b));
}

int n, m;
int pre[SIZE], mx[SIZE], dp[SIZE][2];

void solve() {
    cin >> n >> m;
    build (1, 0, n);
    FOR (t, 0, 1) for (; cnt[t]; cnt[t]--) root[cnt[t]][t] = 0;
    FOR (i, 1, n) {
        int a;
        cin >> a;
        mx[i] = 0;
        pre[i] = pre[i - 1] + a;
    }
    while (m--) {
        int a, b;
        cin >> a >> b;
        mx[b] = max (mx[b], a);
    }
    update (1, 0, n, 0, Line (0, 0), 0);
    FOR (i, 1, n) {
        mx[i] = max (mx[i], mx[i - 1]);
        dp[i][0] = query (1, mx[i], i - 1, 0, n, 2 * pre[i] - pre[n], 0) + (pre[n] - pre[i]) * pre[i];
        dp[i][1] = query (1, mx[i], i - 1, 0, n, 2 * pre[i] - pre[n], 1) + (pre[n] - pre[i]) * pre[i];
        dp[i][1] = max (dp[i][1], dp[i - 1][0] + (pre[n] - pre[i] + pre[i - 1]) * (pre[i] - pre[i - 1]));
        update (1, 0, n, i, Line (pre[i], dp[i][0] - pre[i] * pre[i]), 0);
        update (1, 0, n, i, Line (pre[i], dp[i][1] - pre[i] * pre[i]), 1);
    }
    cout << dp[n][1] / 2 << '\n';
}

int32_t main() {
    Waimai;
    int tt;
    cin >> tt;
    while (tt--) solve();
}

我的分享就到這裡結束了，如果喜歡我的 $\text{Blog}$，歡迎追蹤！