Codeforces

Codeforces 834D

https://codeforces.com/contest/833/problem/B
這題是要把長度為n數列a分成k段，要最大化每一段數字總類的和。

這題很顯然是用DP做，定義dp[i][j]為前i個數字切成j段，然後開一個pre陣列來維護該位置的值前一個相同的地方在哪裡，，對於每個a[i]，只會對[pre[i], i - 1]造成影響，這樣轉移時只要根據pre陣列就能用O(n)，時間複雜度為O(n^2k)，需用線段樹加速轉移。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
#include <bits/stdc++.h>
using namespace std;
vector<int> dp, pre, last;

struct Node{
    int val, tag;
    Node *lc, *rc;
    Node(): lc(nullptr), rc(nullptr), tag(0){}
    void pull()
    {
        if(lc == nullptr)
        {
            val = rc->val;
        }
        else if(rc == nullptr)
        {
            val = lc->val;
        }
        else
        {
            val = max(lc->val, rc->val);
        }
        
    }
    void push()
    {
        if(lc != nullptr)
        {
            lc->tag += tag;
            lc->val += tag;
        }
        if(rc != nullptr)
        {
            rc->tag += tag;
            rc->val += tag;
        }
        tag = 0;
    }
};

Node* build(int L, int R)
{
    Node *node = new Node();
    if(L == R)
    {
        node->val = dp[L];
        return node;
    }
    int M = (L + R) >> 1;
    node->lc = build(L, M);
    node->rc = build(M + 1, R);
    node->pull();
    return node;
}

void update(Node *node, int L, int R, int qL, int qR, int v)
{
    if(qL <= L && R <= qR)
    {
        node->val += v;
        node->tag += v;
        return;
    }
    node->push();
    int M = (L + R) >> 1;
    if(qR <= M)
    {
        update(node->lc, L, M, qL, qR, v);
    }
    else if(M < qL)
    {
        update(node->rc, M + 1, R, qL, qR, v);
    }
    else
    {
        update(node->lc, L, M, qL, qR, v);
        update(node->rc, M + 1, R, qL, qR, v);
    }
    node->pull();
    return;
}

int query(Node *node, int L, int R, int qL, int qR)
{
    if(qL <= L && R <= qR)
    {
        return node->val;
    }
    node->push();
    int M = (L + R) >> 1;
    if(qR <= M)
    {
        return query(node->lc, L, M, qL, qR);
    }
    else if (M < qL)
    {
        return query(node->rc, M + 1, R, qL, qR);
    }
    else
    {
        return max(query(node->lc, L, M, qL, qR), query(node->rc, M + 1, R, qL, qR));
    }
    
}

int main()
{
    int n, k;
    cin >> n >> k;
    vector<int> v(n + 5);
    dp.resize(n + 5, 0);
    pre.resize(n + 5);
    last.resize(n + 5, 0);
    for(int i = 1; i <= n; ++i)
    {
        cin >> v[i];
        pre[i] = last[v[i]];
        last[v[i]] = i;
    }
    dp[0] = 0;
    Node *root;
    for(int j = 1; j <= k; ++j)
    {
        root = build(0, n);
        for(int i = 1; i <= n; ++i)
        {
            update(root, 0, n, pre[i], i - 1, 1);
            dp[i] = query(root, 0, n, 0, i - 1);
            // cout << j << ' ' << i << ' ' << dp[i] << '\n';
        }
    }
    cout << dp[n] << '\n';
}

如果你覺得這篇文章很棒，請你不吝點讚 (ﾟ∀ﾟ)

Recommended Posts