首页 > 其他分享 >20240704

20240704

时间：2024-07-07 14:30:19浏览次数：16  
标签：return Matrix 20240704 int max min inf

NFLSOJ

T2

CF1076G Array Game

阿瑞游戏。

考虑从后往前推。如果一个位置后面能走到的位置中有一个必败态，则一定会走过去，则当前位为必胜态。否则两人必然在当前位反复磨，直到一方不得不滚蛋为止。不得不滚蛋的那位就输了。因此当前位是否必胜只与当前位的奇偶性与后 \(m\) 位的状态有关。由于 \(m\) 很小，考虑直接压成一个数，对每一位记录后面 \(m\) 位的状态，转移相当于根据这些状态推出当前状态，然后把当前状态也扔到状态里，然后转移到（序列的）前一位。注意到这实际上是一个只与奇偶性有关的状态的映射，而且定义域很小。我们直接拿数组记下这个映射，放到线段树上维护。区间加法考虑若加的是偶数，则相当于没变。否则相当于把区间中所有数奇偶性取反。由于每个叶子的映射只有两种，而且一旦取反就是对整个区间取反，所以我们对每个点都记两种映射，要取反就把两个映射交换。最后合并的时候注意映射合并的方向。

代码 
#include <iostream>
#define int long long
using namespace std;
int n, m, q;
int a[200005];
struct f {
    short a[33];
    short& operator[](int x) { return a[x]; }
} T[800005][2];
f A[2];
f operator*(f a, f b) {
    f c;
    for (int i = 0; i < (1 << m); i++) c[i] = b[a[i]];
    return c;
}
struct Segment_Tree {
    bool tg[1000005];
    void tag(int o) {
        tg[o] ^= 1;
        swap(T[o][0], T[o][1]);
    }
    void pushdown(int o) {
        if (!tg[o]) 
            return;
        tag(o << 1);
        tag(o << 1 | 1);
        tg[o] = 0;
    }
    void Build(int o, int l, int r) {
        if (l == r) {
            T[o][0] = A[a[l] & 1];
            T[o][1] = A[!(a[r] & 1)];
            return;
        }
        int mid = (l + r) >> 1;
        Build(o << 1, l, mid);
        Build(o << 1 | 1, mid + 1, r);
        T[o][0] = T[o << 1 | 1][0] * T[o << 1][0];
        T[o][1] = T[o << 1 | 1][1] * T[o << 1][1];
    }
    void Change(int o, int l, int r, int L, int R) {
        if (L <= l && r <= R) {
            tag(o);
            return;
        }
        pushdown(o);
        int mid = (l + r) >> 1;
        if (L <= mid) 
            Change(o << 1, l, mid, L, R);
        if (R > mid) 
            Change(o << 1 | 1, mid + 1, r, L, R);
        T[o][0] = T[o << 1 | 1][0] * T[o << 1][0];
        T[o][1] = T[o << 1 | 1][1] * T[o << 1][1];
    }
    f Query(int o, int l, int r, int L, int R) {
        if (L <= l && r <= R) 
            return T[o][0];
        pushdown(o);
        int mid = (l + r) >> 1;
        if (R <= mid) 
            return Query(o << 1, l, mid, L, R);
        if (L > mid) 
            return Query(o << 1 | 1, mid + 1, r, L, R);
        return Query(o << 1 | 1, mid + 1, r, L, R) * Query(o << 1, l, mid, L, R);
    }
} seg;
signed main() {
    cin >> n >> m >> q;
    for (int i = 1; i <= n; i++) cin >> a[i];
    for (short i = 0; i < (1 << m); i++) {
        if (i != (1 << m) - 1) 
            A[0][i] = A[1][i] = (i << 1 | 1);
        else {
            A[0][i] = (i << 1 | 1);
            A[1][i] = (i << 1);
        }
        if (i & (1 << (m - 1)))  
            A[0][i] ^= (1 << m), A[1][i] ^= (1 << m);
    }
    seg.Build(1, 1, n);
    while (q--) {
        int op, l, r, d;
        cin >> op;
        if (op == 1) {
            cin >> l >> r >> d;
            if (d & 1)
                seg.Change(1, 1, n, l, r);
        } else {
            cin >> l >> r;
            f tmp = seg.Query(1, 1, n, l, r);
            cout << 2 - (tmp[(1 << m) - 1] & 1) << "\n";
        }
    }
    return 0;
}

T3

CF1681E Labyrinth Adventures

考虑在层之间做转移。注意到一个层的有效位置只有两个，也就是两个门的位置。层之间的转移都是线性的，可以直接使用矩阵刻画。询问的时候区间矩阵乘起来，再加上两头走到门的距离即可。

代码 
#include <iostream>
#define int long long
using namespace std;
const int inf = 1000000000;
int n, m;
struct node {
    int x, y;
} d[100005][2];
struct Matrix {
    int a[2][2];
    int* operator[](int x) { return a[x]; }
} T[400005], I, A[400005];
Matrix operator*(Matrix a, Matrix b) {
    Matrix c;
    c[0][0] = min(a[0][0] + b[0][0], a[0][1] + b[1][0]);
    c[0][1] = min(a[0][0] + b[0][1], a[0][1] + b[1][1]);
    c[1][0] = min(a[1][0] + b[0][0], a[1][1] + b[1][0]);
    c[1][1] = min(a[1][0] + b[0][1], a[1][1] + b[1][1]);
    return c;
}
struct Segment_Tree {
    void Build(int o, int l, int r) {
        if (l == r) {
            T[o] = A[l];
            return;
        }
        int mid = (l + r) >> 1;
        Build(o << 1, l, mid);
        Build(o << 1 | 1, mid + 1, r);
        T[o] = T[o << 1] * T[o << 1 | 1];
    }
    Matrix Query(int o, int l, int r, int L, int R) {
        if (L <= l && r <= R) 
            return T[o];
        int mid = (l + r) >> 1;
        if (R <= mid) 
            return Query(o << 1, l, mid, L, R);
        if (L > mid) 
            return Query(o << 1 | 1, mid + 1, r, L, R);
        return Query(o << 1, l, mid, L, R) * Query(o << 1 | 1, mid + 1, r, L, R);
    }
} seg;
signed main() {
    cin >> n;
    for (int i = 1; i < n; i++) cin >> d[i][0].y >> d[i][0].x >> d[i][1].y >> d[i][1].x;
    for (int i = 1; i < n - 1; i++) {
        A[i][0][0] = (abs(d[i + 1][0].x - d[i][0].x));
        A[i][1][1] = (abs(d[i + 1][1].y - d[i][1].y));
        A[i][0][1] = (abs(d[i + 1][1].x - d[i][0].x)) + abs(d[i][0].y + 1 - d[i + 1][1].y);
        A[i][1][0] = (abs(d[i + 1][0].y - d[i][1].y)) + abs(d[i][1].x + 1 - d[i + 1][0].x);
    }
    if (n != 2) 
        seg.Build(1, 1, n - 2);
    cin >> m;
    while (m--) {
        int x1, y1, x2, y2;
        cin >> y1 >> x1 >> y2 >> x2;
        int ca = max(x1, y1);
        int cb = max(x2, y2);
        if (ca > cb) 
            swap(x1, x2), swap(y1, y2), swap(ca, cb);
        if (ca != cb) {
            --cb;
            int a = abs(x1 - d[ca][0].x) + abs(y1 - d[ca][0].y);
            int b = abs(x1 - d[ca][1].x) + abs(y1 - d[ca][1].y);
            int c = abs(x2 - d[cb][0].x) + abs(y2 - d[cb][0].y - 1) + 1;
            int e = abs(x2 - d[cb][1].x - 1) + abs(y2 - d[cb][1].y) + 1;
            I[0][0] = a, I[0][1] = b;
            I[1][0] = I[1][1] = inf;
            if (ca <= cb - 1) 
                I = I * seg.Query(1, 1, n - 2, ca, cb - 1);
            cout << min(I[0][0] + c, I[0][1] + e) + cb - ca << "\n";
        } else 
            cout << abs(x1 - x2) + abs(y1 - y2) << "\n";
    }
    return 0;
}

T4

CF1609E William the Obvilious

从前往后考虑，我们只关注当前匹配到 \(\texttt{abc}\) 的哪一位，因此把这个东西扔到状态里。转移都是线性的，矩乘刻画一下即可。

代码 
#include <iostream>
#define int long long
using namespace std;
const int inf = 1000000000;
int n, q;
string str;
struct Matrix {
    int a[3][3];
    int* operator[](int x) { return a[x]; }
} M[3], T[400005], I;
Matrix operator*(Matrix a, Matrix b) {
    Matrix c;
    c[0][0] = min(a[0][0] + b[0][0], min(a[0][1] + b[1][0], a[0][2] + b[2][0]));
    c[0][1] = min(a[0][0] + b[0][1], min(a[0][1] + b[1][1], a[0][2] + b[2][1]));
    c[0][2] = min(a[0][0] + b[0][2], min(a[0][1] + b[1][2], a[0][2] + b[2][2]));
    c[1][0] = min(a[1][0] + b[0][0], min(a[1][1] + b[1][0], a[1][2] + b[2][0]));
    c[1][1] = min(a[1][0] + b[0][1], min(a[1][1] + b[1][1], a[1][2] + b[2][1]));
    c[1][2] = min(a[1][0] + b[0][2], min(a[1][1] + b[1][2], a[1][2] + b[2][2]));
    c[2][0] = min(a[2][0] + b[0][0], min(a[2][1] + b[1][0], a[2][2] + b[2][0]));
    c[2][1] = min(a[2][0] + b[0][1], min(a[2][1] + b[1][1], a[2][2] + b[2][1]));
    c[2][2] = min(a[2][0] + b[0][2], min(a[2][1] + b[1][2], a[2][2] + b[2][2]));
    return c;
}
struct Segment_Tree {
    void Build(int o, int l, int r) {
        if (l == r) {
            T[o] = M[str[l] - 'a'];
            return;
        }
        int mid = (l + r) >> 1;
        Build(o << 1, l, mid);
        Build(o << 1 | 1, mid + 1, r);
        T[o] = T[o << 1] * T[o << 1 | 1];
    }
    void Change(int o, int l, int r, int x) {
        if (l == r) {
            T[o] = M[str[x] - 'a'];
            return;
        }
        int mid = (l + r) >> 1;
        if (x <= mid) 
            Change(o << 1, l, mid, x);
        else 
            Change(o << 1 | 1, mid + 1, r, x);
        T[o] = T[o << 1] * T[o << 1 | 1];
    }
} seg;
signed main() {
    cin >> n >> q;
    cin >> str;
    str = ' ' + str;
    M[0][0][0] = 1,   M[0][0][1] = 0,   M[0][0][2] = inf;
    M[0][1][0] = inf, M[0][1][1] = 0,   M[0][1][2] = 1;
    M[0][2][0] = inf, M[0][2][1] = inf, M[0][2][2] = 0;
    M[1][0][0] = 0,   M[1][0][1] = 1,   M[1][0][2] = inf;
    M[1][1][0] = inf, M[1][1][1] = 1,   M[1][1][2] = 0;
    M[1][2][0] = inf, M[1][2][1] = inf, M[1][2][2] = 0;
    M[2][0][0] = 0,   M[2][0][1] = 1,   M[2][0][2] = inf;
    M[2][1][0] = inf, M[2][1][1] = 0,   M[2][1][2] = 1;
    M[2][2][0] = inf, M[2][2][1] = inf, M[2][2][2] = 1;
    seg.Build(1, 1, n);
    while (q--) {
        int x;
        char y;
        cin >> x >> y;
        str[x] = y;
        seg.Change(1, 1, n, x);
        I[0][0] = 0;
        I[0][1] = I[0][2] = inf;
        I[1][0] = I[1][1] = I[1][2] = inf;
        I[2][0] = I[2][1] = I[2][2] = inf;
        I = I * T[1];
        cout << min(I[0][0], min(I[0][1], I[0][2])) << "\n";
    }
    return 0;
}

T5

CF750E New Year and Old Subsequence

从前往后考虑，我们只关注当前匹配到 \(\texttt{2017}\) 和 \(\texttt{2016}\) 的哪一位。把这个东西扔到状态里，注意当匹配到 \(1\) 及其后的位时要对于 \(6\) 特殊转移，防止出现 \(\texttt{2016}\)。

代码 
#include <iostream>
#define int long long
using namespace std;
const int inf = 2147483647;
int n, q;
string str;
struct Matrix {
    int a[5][5];
    int* operator[](int x) { return a[x]; }
} T[800005], A[10], I, E;
Matrix operator*(Matrix a, Matrix b) {
    Matrix c;
    for (int i = 0; i < 5; i++) {
        for (int j = 0; j < 5; j++) {
            c[i][j] = inf;
            for (int k = 0; k < 5; k++) 
                c[i][j] = min(c[i][j], a[i][k] + b[k][j]);
        }
    }
    return c;
}
struct Segment_Tree {
    void Build(int o, int l, int r) {
        if (l == r) {
            T[o] = A[str[l] - '0'];
            return;
        }
        int mid = (l + r) >> 1;
        Build(o << 1, l, mid);
        Build(o << 1 | 1, mid + 1, r);
        T[o] = T[o << 1] * T[o << 1 | 1];
    }
    Matrix Query(int o, int l, int r, int L, int R) {
        if (L <= l && r <= R) 
            return T[o];
        int mid = (l + r) >> 1;
        if (R <= mid) 
            return Query(o << 1, l, mid, L, R);
        if (L > mid) 
            return Query(o << 1 | 1, mid + 1, r, L, R);
        return Query(o << 1, l, mid, L, R) * Query(o << 1 | 1, mid + 1, r, L, R);
    }
} seg;
signed main() {
    cin >> n >> q;
    cin >> str;
    str = ' ' + str;
    for (int i = 0; i < 5; i++) {
        for (int j = 0; j < 5; j++) 
            E[i][j] = (i == j ? 0 : inf);
    }
    for (int i = 0; i < 10; i++) {
        A[i] = E;
        if (i != 0 && i != 1 && i != 2 && i != 6 && i != 7) 
            continue;
        else if (i == 2) 
            A[i][0][0] = 1, A[i][0][1] = 0;
        else if (i == 0) 
            A[i][1][1] = 1, A[i][1][2] = 0;
        else if (i == 1) 
            A[i][2][2] = 1, A[i][2][3] = 0;
        else if (i == 7) 
            A[i][3][3] = 1, A[i][3][4] = 0;
        else 
            A[i][3][3] = 1, A[i][4][4] = 1;
    }
    seg.Build(1, 1, n);
    while (q--) {
        int l, r;
        cin >> l >> r;
        I[0][0] = 0, I[0][1] = inf, I[0][2] = inf, I[0][3] = inf, I[0][4] = inf;
        I[1][0] = inf, I[1][1] = inf, I[1][2] = inf, I[1][3] = inf, I[1][4] = inf;
        I[2][0] = inf, I[2][1] = inf, I[2][2] = inf, I[2][3] = inf, I[2][4] = inf;
        I[3][0] = inf, I[3][1] = inf, I[3][2] = inf, I[3][3] = inf, I[3][4] = inf;
        I[4][0] = inf, I[4][1] = inf, I[4][2] = inf, I[4][3] = inf, I[4][4] = inf;
        I = I * seg.Query(1, 1, n, l, r);
        cout << (I[0][4] >= inf ? -1 : I[0][4]) << "\n";
    }
    return 0;
}

T6

CF1192B Dynamic Diameter

考虑动态 dp。先把边权下放到点权，设 \(f[i][0 / 1]\) 表示 \(i\) 子树内（包括 \(i\) 向上的边）的直径和还能向上延伸的最长链。重剖一下，将重儿子以外的 dp 值和当前点权视为常数，这些东西对重儿子 dp 值转移到当前点 dp 值的贡献可以使用矩阵刻画。这个矩阵可以根据转移方程列一下，应当是好列的。接下来考虑修改。首先对于一个点，如果知道其所有轻儿子的 dp 值，则可以根据当前点权构造出当前点的转移矩阵。也就是修改一个点实际上是修改了它的矩阵。这个矩阵更改后会直接影响到其所在链顶的 dp 值，所以这个链顶的 dp 值必须重新计算。由于链顶是轻儿子，而轻儿子的 dp 值变动会导致其父亲的转移矩阵变化，所以还需要重新计算链顶父亲的转移矩阵。然后依次类推，直到更新到根为止。重新计算某个点 dp 值的方法很简单，由于链底必为叶子，直接用这个叶子的初始矩阵按顺序乘上链上所有点的转移矩阵即可。线段树维护转移矩阵，需要注意矩阵乘法的方向。

代码 
#include <iostream>
#include <set>
#define int long long
using namespace std;
const int inf = 4000000000000000000;
int n, q, W;
int head[100005], nxt[200005], to[200005], ew[200005], ecnt;
void add(int u, int v, int ww) { to[++ecnt] = v, nxt[ecnt] = head[u], head[u] = ecnt, ew[ecnt] = ww; }
int down[100005], _dfn[100005], son[100005], top[100005], dfn[100005], dep[100005], sz[100005], fa[100005], w[100005], ncnt;
int eu[100005], ev[100005];
int f[100005][2];
multiset<int, greater<int> > st[100005][2];
struct Matrix {
    int a[3][3];
    int* operator[](int x) { return a[x]; }
    Matrix() { a[0][0] = a[0][1] = a[0][2] = a[1][0] = a[1][1] = a[1][2] = a[2][0] = a[2][1] = a[2][2] = -inf; }
} A[100005], T[400005], E;
Matrix operator*(Matrix a, Matrix b) {
    Matrix c;
    c[0][0] = max(a[0][0] + b[0][0], max(a[0][1] + b[1][0], a[0][2] + b[2][0]));
    c[0][1] = max(a[0][0] + b[0][1], max(a[0][1] + b[1][1], a[0][2] + b[2][1]));
    c[0][2] = max(a[0][0] + b[0][2], max(a[0][1] + b[1][2], a[0][2] + b[2][2]));
    c[1][0] = max(a[1][0] + b[0][0], max(a[1][1] + b[1][0], a[1][2] + b[2][0]));
    c[1][1] = max(a[1][0] + b[0][1], max(a[1][1] + b[1][1], a[1][2] + b[2][1]));
    c[1][2] = max(a[1][0] + b[0][2], max(a[1][1] + b[1][2], a[1][2] + b[2][2]));
    c[2][0] = max(a[2][0] + b[0][0], max(a[2][1] + b[1][0], a[2][2] + b[2][0]));
    c[2][1] = max(a[2][0] + b[0][1], max(a[2][1] + b[1][1], a[2][2] + b[2][1]));
    c[2][2] = max(a[2][0] + b[0][2], max(a[2][1] + b[1][2], a[2][2] + b[2][2]));
    return c;
}
Matrix Construct(int x) {
    if (!son[x]) 
        return E;
    int g0, g1 = *st[x][1].begin();
    if (sz[son[x]] + 1 == sz[x]) 
        g0 = *st[x][0].begin();
    else {
        int tmp = *st[x][1].begin();
        st[x][1].erase(st[x][1].begin());
        g0 = max(*st[x][0].begin(), tmp + *st[x][1].begin());
        st[x][1].insert(tmp);
    }
    g1 += w[x];
    Matrix ret;
    ret[0][0] = ret[2][2] = 0;
    ret[1][0] = g1 - w[x];
    ret[2][1] = g1;
    ret[2][0] = g0;
    ret[1][1] = w[x];
    return ret;
}
void dfs1(int x, int fa, int d) {
    dep[x] = d;
    ::fa[x] = fa;
    sz[x] = 1;
    for (int i = head[x]; i; i = nxt[i]) {
        int v = to[i];
        if (v != fa) {
            w[v] = ew[i];
            dfs1(v, x, d + 1);
            sz[x] += sz[v];
            if (sz[v] > sz[son[x]]) 
                son[x] = v;
        }
    }
}
void dfs2(int x, int t) {
    top[x] = t;
    _dfn[dfn[x] = ++ncnt] = x;
    if (!son[x]) {
        down[t] = x;
        return;
    }
    dfs2(son[x], t);
    for (int i = head[x]; i; i = nxt[i]) {
        int v = to[i];
        if (v != fa[x] && v != son[x]) 
            dfs2(v, v);
    }
}
void dfs3(int x) {
    f[x][1] = w[x];
    for (int i = head[x]; i; i = nxt[i]) {
        int v = to[i];
        if (v != fa[x]) {
            dfs3(v);
            f[x][0] = max(f[x][0], max(f[v][0], f[x][1] - w[x] + f[v][1]));
            f[x][1] = max(f[x][1], f[v][1] + w[x]);
            if (v != son[x]) {
                st[x][0].insert(f[v][0]);
                st[x][1].insert(f[v][1]);
            }
        }
    }
    if (son[x])
        A[dfn[x]] = Construct(x);
    else 
        A[dfn[x]] = E;
}
struct Segment_Tree {
    void Build(int o, int l, int r) {
        if (l == r) {
            T[o] = A[l];
            return;
        }
        int mid = (l + r) >> 1;
        Build(o << 1, l, mid);
        Build(o << 1 | 1, mid + 1, r);
        T[o] = T[o << 1 | 1] * T[o << 1];
    }
    void Change(int o, int l, int r, int x) {
        if (l == r) {
            T[o] = A[l];
            return;
        }
        int mid = (l + r) >> 1;
        if (x <= mid) 
            Change(o << 1, l, mid, x);
        else 
            Change(o << 1 | 1, mid + 1, r, x);
        T[o] = T[o << 1 | 1] * T[o << 1];
    }
    Matrix Query(int o, int l, int r, int L, int R) {
        if (L > R) 
            return E;
        if (L <= l && r <= R) 
            return T[o];
        int mid = (l + r) >> 1;
        if (R <= mid) 
            return Query(o << 1, l, mid, L, R);
        if (L > mid) 
            return Query(o << 1 | 1, mid + 1, r, L, R);
        return  Query(o << 1 | 1, mid + 1, r, L, R) * Query(o << 1, l, mid, L, R);
    }
} seg;
void Change(int x) {
    if (son[x]) {
        A[dfn[x]] = Construct(x);
        seg.Change(1, 1, n, dfn[x]);
    }
    Matrix I;
    while (1) {
        int tmp = down[top[x]];
        I[0][0] = I[0][2] = 0, I[0][1] = w[tmp];
        I = I * seg.Query(1, 1, n, dfn[top[x]], dfn[tmp] - 1);
        x = top[x];
        int tmp0 = f[x][0], tmp1 = f[x][1];
        f[x][0] = I[0][0], f[x][1] = I[0][1];
        if (x == 1) 
            break;
        st[fa[x]][0].erase(st[fa[x]][0].find(tmp0));
        st[fa[x]][1].erase(st[fa[x]][1].find(tmp1));
        st[fa[x]][0].insert(f[x][0]);
        st[fa[x]][1].insert(f[x][1]);
        x = fa[x];
        A[dfn[x]] = Construct(x);
        seg.Change(1, 1, n, dfn[x]);
    }
}
signed main() {
    E[0][0] = E[1][1] = E[2][2] = 0;
    cin >> n >> q >> W;
    for (int i = 1; i < n; i++) {
        int ww;
        int &u = eu[i], &v = ev[i];
        cin >> u >> v >> ww;
        add(u, v, ww);
        add(v, u, ww);
    }
    dfs1(1, 0, 1);
    dfs2(1, 1);
    dfs3(1);
    seg.Build(1, 1, n);
    int lans = 0;
    while (q--) {
        int d, ww;
        cin >> d >> ww;
        d = (d + lans) % (n - 1) + 1;
        ww = (ww + lans) % W;
        if (dep[eu[d]] < dep[ev[d]]) {
            w[ev[d]] = ww;
            Change(ev[d]);
        } else {
            w[eu[d]] = ww;
            Change(eu[d]);
        }
        cout << (lans = max(f[1][1], f[1][0])) << "\n";
    }
    return 0;
}

T10

Atcoder ABC228H Histogram

先排序，考虑最终的序列一定是一段一段，每一段都与最后一个数相同，而这最后一个数一直不变。因此直接 dp，发现可以斜率优化，然后就做完了。

代码 
#include <iostream>
#include <algorithm>
#define int long long
using namespace std;
pair<int, int> a[200005];
int S[2][200005];
int n, X;
struct Line {
    int k, b;
    int operator()(int x) { return k * x + b; }
} stk[200005];
int sz;
bool chk(Line a, Line b, Line c) { return (b.b - a.b) * (b.k - c.k) >= (c.b - b.b) * (a.k - b.k); }
int dp[200005];
signed main() {
    cin >> n >> X;
    for (int i = 1; i <= n; i++) cin >> a[i].first >> a[i].second;
    sort(a + 1, a + n + 1);
    for (int i = 1; i <= n; i++) S[0][i] = S[0][i - 1] + a[i].second, S[1][i] = S[1][i - 1] + a[i].first * a[i].second;
    stk[++sz] = (Line) { 0, 0 };
    for (int i = 1, j = 1; i <= n; i++) {
        int x = a[i].first;
        while (j < sz && stk[j](x) >= stk[j + 1](x)) ++j;
        dp[i] = stk[j](x) - S[1][i] + a[i].first * S[0][i] + X;
        Line tmp = (Line) { -S[0][i], S[1][i] + dp[i] };
        while (sz > j && chk(stk[sz - 1], stk[sz], tmp)) --sz;
        stk[++sz] = tmp;
    }
    cout << dp[n] << "\n";
    return 0;
}
···
</details>

### T11
CF1527E Partition Game

直接线段树优化 dp 即可。也可以根据决策单调性分治。

<details>
<summary> 代码 </summary>

```cpp
#include <iostream>
#include <string.h>
#define int long long
using namespace std;
int n, k;
int f[35005][105];
int ap[35005];
int a[35005];
struct Segment_Tree {
    int mx[140005], tg[140005];
    void tag(int o, int v) { tg[o] += v, mx[o] += v; }
    void pushdown(int o) {
        if (!tg[o]) 
            return;
        tag(o << 1, tg[o]);
        tag(o << 1 | 1, tg[o]);
        tg[o] = 0;
    }
    void Build(int o, int l, int r, int k) {
        tg[o] = 0;
        if (l == r) {
            mx[o] = f[l][k];
            return;
        }
        int mid = (l + r) >> 1;
        Build(o << 1, l, mid, k);
        Build(o << 1 | 1, mid + 1, r, k);
        mx[o] = min(mx[o << 1], mx[o << 1 | 1]);
    }
    void Add(int o, int l, int r, int L, int R, int v) {
        if (L <= l && r <= R) {
            tag(o, v);
            return;
        }
        pushdown(o);
        int mid = (l + r) >> 1;
        if (L <= mid) 
            Add(o << 1, l, mid, L, R, v);
        if (R > mid) 
            Add(o << 1 | 1, mid + 1, r, L, R, v);
        mx[o] = min(mx[o << 1], mx[o << 1 | 1]);
    }
    int Query(int o, int l, int r, int L, int R) {
        if (L <= l && r <= R) 
            return mx[o];
        pushdown(o);
        int mid = (l + r) >> 1;
        if (R <= mid) 
            return Query(o << 1, l, mid, L, R);
        if (L > mid) 
            return Query(o << 1 | 1, mid + 1, r, L, R);
        return min(Query(o << 1, l, mid, L, R), Query(o << 1 | 1, mid + 1, r, L, R));
    }
} seg;
signed main() {
    cin >> n >> k;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        if (ap[a[i]]) 
            f[i][1] = f[i - 1][1] + i - ap[a[i]];
        else 
            f[i][1] = f[i - 1][1];
        ap[a[i]] = i;
    }
    seg.Build(1, 1, n, 1);
    for (int x = 2; x <= k; x++) {
        memset(ap, 0, sizeof ap);
        f[1][x] = 0;
        ap[a[1]] = 1;
        for (int i = 2; i <= n; i++) {
            if (ap[a[i]] > 1) 
                seg.Add(1, 1, n, 1, ap[a[i]] - 1, i - ap[a[i]]);
            ap[a[i]] = i;
            f[i][x] = seg.Query(1, 1, n, 1, i - 1);
        }
        seg.Build(1, 1, n, x);
    }
    cout << f[n][k] << "\n";
    return 0;
}

标签：return,Matrix,20240704,int,max,min,inf
From： https://www.cnblogs.com/forgotmyhandle/p/18288473

相关文章

  • YC314A [ 20240704 CQYC省选模拟赛 T1 ] 士兵（solider）
    题意给定一张\(n\)个点\(m\)条边的有向图，每条边上有一个字母。\(q\)次询问，每次询问\(s\tot\)中的最短回文路径的长度是多少。\(n\le10^3,m\le10^5\)Sol区间\(\text{dp}\)，设\(f_{i,j}\)表示从\(i\)到\(j\)的最短回文路径的长度。每次枚举一条边\(......
  • 程序人生日记20240704|工作零食：米饭+十分米莲藕汁+饼干（减脂记录）
    程序员的工作饮食减脂记录打卡餐别：早餐零食详情：（同事给的不算统计内）零食名称：十分米莲藕汁配饼干其他选择：米饭+海盐饼干。大致热量估算：莲藕汁约50卡，低脂全麦饼干2片约80卡，米饭约500卡，总计约630卡。初始数据：体重：90公斤目标：80公斤完成情况：完成。程序员自律宣言：程序猿不可以......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99