这篇博文探讨了单调队列优化dp的一些实践

单调队列优化dp

决策单调性

Acwing331

Acwing331-01
Acwing331-02

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
template <class T>
inline bool chmax(T& a, T b) {
    if(a < b) {
        a = b;
        return true;
    }
    return false;
}

template <class T>
inline bool chmin(T& a, T b) {
    if(a > b) {
        a = b;
        return true;
    }
    return false;
}

// ============================================================== //

const int maxn = 1e5 + 10;
const int inf = 0x3f3f3f3f;
int n, a[maxn];
int S[maxn], que[maxn];
int f[maxn], h[maxn];

inline int calc(int j) {
    return f[j] + S[j];
}

void dp() {
    int l = 1, r = 1;
    que[l] = 0;
    int p = 0;
    _rep(i, 1, n) {
        while (l <= r && f[que[l]] <= S[i] - S[que[l]]) chmax(p, que[l]), l++;
        h[i] = h[p] + 1;
        f[i] = S[i] - S[p];

        while (l <= r && calc(que[r]) >= calc(i)) r--;
        que[++r] = i;
    }
}

void init() {
    memset(S, 0, sizeof(S));
    memset(que, 0, sizeof(que));
}

int main() {
    freopen("input.txt", "r", stdin);
    init();
    cin >> n;
    _forDown(i, n, 1) {
        scanf("%d", &a[i]);
    }
    _rep(i, 1, n) S[i] = S[i-1] + a[i];

    // then dp
    dp();
    int ans = h[n];
    printf("%d\n", ans);
}

单调队列优化

SCOI2010 股票交易

SCOI2010
SCOI2010
SCOI2010

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
const int maxn = 2000 + 5;
const int maxm = 50 + 5;
int maxp, n, w;
int ap[maxn], as[maxn], bp[maxn], bs[maxn];
const int inf = 0x3f3f3f3f;

ll f[maxn][maxn], pre[maxn];
ll que[maxn];

inline ll calc(ll k, ll v) {
    return pre[k] + 1ll * k * v;
}

void dp() {
    memset(f, -inf, sizeof(f));
    memset(pre, -inf, sizeof(pre));
    memset(que, 0, sizeof(que));
    pre[0] = 0;

    _rep(i, 1, n) {
        _rep(k, 0, maxp) if(i > w+1) chmax(pre[k], f[i-w-1][k]);

        int l = 1, r = 0;
        _rep(j, 0, maxp) {
            while (l <= r && que[l] < j - as[i]) l++;
            if(l <= r) chmax(f[i][j], -j*ap[i] + calc(que[l], ap[i]));
            while (l <= r && calc(que[r], ap[i]) <= calc(j, ap[i])) r--;
            que[++r] = j;
        }

        l = 1, r = 0;
        _forDown(j, maxp, 0) {
            while (l <= r && que[l] > j + bs[i]) l++;
            if(l <= r) chmax(f[i][j], -j*bp[i] + calc(que[l], bp[i]));
            while (l <= r && calc(que[r], bp[i]) <= calc(j, bp[i])) r--;
            que[++r] = j;
        }
        _rep(j, 0, maxp) chmax(f[i][j], f[i-1][j]);
    }
}

void init() {
    //
}

int main() {
    freopen("input.txt", "r", stdin);
    init();
    // get data
    cin >> n >> maxp >> w;
    _rep(i, 1, n) {
        scanf("%d%d%d%d", &ap[i], &bp[i], &as[i], &bs[i]);
    }

    // then dp
    dp();
    ll ans = 0;
    _rep(j, 0, maxp) chmax(ans, f[n][j]);
    printf("%lld\n", ans);
}

单调栈性质

HDU2870

1
2
3
4
5
6
7
8
9
10
l[i] 表示下标 i 左边第一个比 i 小的元素的索引
int stk[maxn];

int top = 0;
for(int i = 0; i < n; i++) {
    while (top && arr[stk[top]] >= arr[i]) top--;
    if(top == 0) l[i] = 0;
    else l[i] = stk[top];
    stk[++top] = i;
}

HDU1506

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

const int maxn = 100000 + 10;
int stk[maxn], l[maxn], r[maxn];
ll h[maxn];

void solve(int n) {
    int top = 0;
    _for(i, 0, n) {
        while (top && h[stk[top]] >= h[i]) top--;
        if(top == 0) l[i] = 0;
        else l[i] = stk[top] + 1;
        stk[++top] = i;
    }

    top = 0;
    _forDown(i, n-1, 0) {
        while (top && h[stk[top]] >= h[i]) top--;
        if(top == 0) r[i] = n;
        else r[i] = stk[top];
        stk[++top] = i;
    }

    ll ans = 0;
    _for(i, 0, n) chmax(ans, 1ll * h[i] * (r[i] - l[i]));
    printf("%lld\n", ans);
}

void init() {
    memset(stk, 0, sizeof(stk));
    memset(l, 0, sizeof(l));
    memset(r, 0, sizeof(r));
}

int main() {
    freopen("input.txt", "r", stdin);
    int n;

    while (~scanf("%d", &n) && n) {
        init();
        _for(i, 0, n) scanf("%lld", &h[i]);

        solve(n);
    }
}

再来看一下这个问题的升级版
HDU2870

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

const int maxn = 1000 + 10;
int n, m;
int a[maxn][maxn], b[maxn][maxn], c[maxn][maxn];
char grid[maxn][maxn];

void prework() {
    _rep(i, 1, n) {
        _for(j, 0, m) {
            const char& cur = grid[i][j];
            if(cur == 'a' || cur == 'w' || cur == 'y' || cur == 'z') {
                a[i][j] = a[i-1][j] + 1;
            }
            else a[i][j] = 0;

            if(cur == 'b' || cur == 'w' || cur == 'x' || cur == 'z') {
                b[i][j] = b[i-1][j] + 1;
            }
            else b[i][j] = 0;

            if(cur == 'c' || cur == 'x' || cur == 'y' || cur == 'z') {
                c[i][j] = c[i-1][j] + 1;
            }
            else c[i][j] = 0;
        }
    }
}

int stk[maxn], l[maxn], r[maxn];

void dp(const int h[][maxn], ll& ans) {
    _rep(i, 1, n) {
        memset(stk, 0, sizeof(stk));
        memset(l, 0, sizeof(l));
        memset(r, 0, sizeof(r));

        int top = 0;
        _for(j, 0, m) {
            while (top && h[i][stk[top]] >= h[i][j]) top--;
            if(top == 0) l[j] = 0;
            else l[j] = stk[top] + 1;
            stk[++top] = j;
        }

        top = 0;
        _forDown(j, m-1, 0) {
            while (top && h[i][stk[top]] >= h[i][j]) top--;
            if(top == 0) r[j] = m;
            else r[j] = stk[top];
            stk[++top] = j;
        }

        _for(j, 0, m) chmax(ans, 1ll * h[i][j] * (r[j] - l[j]));
    }
}

void dbg() {
    _rep(i, 1, n) printf("%s\n", grid[i]);
}

void init() {
    memset(a, 0, sizeof(a));
    memset(b, 0, sizeof(b));
    memset(c, 0, sizeof(c));
}

int main() {
    freopen("input.txt", "r", stdin);
    while (scanf("%d%d", &n, &m) != EOF) {
        init();
        _rep(i, 1, n) {
            getchar();
            scanf("%s", grid[i]);
        }

        //dbg();

        prework();
        ll ans = 0;
        dp(a, ans);
        dp(b, ans);
        dp(c, ans);

        printf("%lld\n", ans);
    }
}

滑动窗口与单调队列

滑动窗口最值问题可以用单调队列求解

滑动窗口

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
const int maxn = 1e6 + 10;
ll a[maxn];
int n, k;

int que[maxn];

void dp1(vector<ll>& vec) {
    memset(que, 0, sizeof(que));
    int l = 1, r = 0;
    _rep(i, 1, k) {
        while (l <= r && a[que[r]] >= a[i]) r--;
        que[++r] = i;
    }

    _rep(i, k, n) {
        int st = i+1-k;
        while (l <= r && que[l] < st) l++;
        while (l <= r && a[que[r]] >= a[i]) r--;
        que[++r] = i;

        vec.push_back(a[que[l]]);
    }
}

void dp2(vector<ll>& vec) {
    memset(que, 0, sizeof(que));
    int l = 1, r = 0;
    _rep(i, 1, k) {
        while (l <= r && a[que[r]] <= a[i]) r--;
        que[++r] = i;
    }

    _rep(i, k, n) {
        int st = i+1-k;
        while (l <= r && que[l] < st) l++;
        while (l <= r && a[que[r]] <= a[i]) r--;
        que[++r] = i;

        vec.push_back(a[que[l]]);
    }
}

void init() {
    //
}

int main() {
    freopen("input.txt", "r", stdin);
    cin >> n >> k;
    init();
    _rep(i, 1, n) scanf("%lld", &a[i]);

    // then solve
    vector<ll> ans1;
    dp1(ans1);
    for(auto x : ans1) printf("%lld ", x);
    printf("\n");

    vector<ll> ans2;
    dp2(ans2);
    for(auto x : ans2) printf("%lld ", x);
}

离散段和线性区间的单调队列

瑰丽华尔兹
NOI2005

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
const int maxn = 200 + 10;
const int inf = 0x3f3f3f3f;
char mp[maxn][maxn];

const int dx[] = {0, -1, 1, 0, 0};
const int dy[] = {0, 0, 0, -1, 1};


int n, m, K;
int sx, sy;
int S[maxn], T[maxn], D[maxn];

bool valid(int x, int y) {
    return 1 <= x && x <= n && 1 <= y && y <= m;
}

void dbg() {
    _rep(i, 1, n) printf("%s", mp[i]+1), printf("\n");
}

int f[maxn][maxn][maxn];
int ans;

class A {
public:
    int f, step;
    A() {}
    A(int f, int step) : f(f), step(step) {}
} que[maxn];

void dp(int i, int x, int y) {
    int L = T[i] - S[i] + 1;
    int d = D[i];

    int num = 0;
    int l = 1, r = 0;
    while (valid(x, y)) {
        if(mp[x][y] == 'x') {
            l = 1, r = 0;
        }
        else {
            if(f[i-1][x][y] != -inf) {
                while (l <= r && que[r].f + num - que[r].step <= f[i-1][x][y]) r--;
                que[++r] = A(f[i-1][x][y], num);
            }
        }

        while (l <= r && num - que[l].step > L) l++;
        if(l <= r) f[i][x][y] = que[l].f + num - que[l].step;
        else f[i][x][y] = -inf;

        chmax(ans, f[i][x][y]);

        num++;
        x += dx[d], y += dy[d];
    }
}


void init() {
    memset(f, -inf, sizeof(f));
    f[0][sx][sy] = 0;
    ans = 0;
}

void solve() {
    init();
    _rep(i, 1, K) {
        int d = D[i];

        if(d == 1) {
            _rep(j, 1, m) dp(i, n, j);
        }
        else if(d == 2) {
            _rep(j, 1, m) dp(i, 1, j);
        }
        else if(d == 3) {
            _rep(j, 1, n) dp(i, j, m);
        }
        else {
            _rep(j, 1, n) dp(i, j, 1);
        }
    }

    printf("%d\n", ans);
}


int main() {
    freopen("input.txt", "r", stdin);
    scanf("%d%d%d%d%d", &n, &m, &sx, &sy, &K);
    _rep(i, 1, n) scanf("%s", mp[i]+1);
    _rep(i, 1, K) scanf("%d%d%d", &S[i], &T[i], &D[i]);

    // dbg();
    // then solve the problem

    solve();
}

单调队列问题总结

CF372C
CF372C

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
const int maxn = 150000 + 10;
const int maxm = 300 + 10;
const ll inf = 0xcfcfcfcfcfcfcfcf;

ll f[2][maxn];
ll a[maxm], b[maxm], t[maxm];
int n, m, d;

int que[maxn];

int fl = 1;
void init() {
    memset(f, inf, sizeof(f));
    memset(que, 0, sizeof(que));
    _rep(i, 1, n) f[0][i] = 0;
    fl = 1;
}



void dp() {
    init();
    _rep(i, 1, m) {
        int l = 1, r = 0;

        int k = 1;
        _rep(j, 1, n) {
            for (; k <= min(1ll*n, j+d*(t[i]-t[i-1])); k++) {
                while (l <= r && f[fl^1][que[r]] <= f[fl^1][k]) r--;
                que[++r] = k;
            }

            while (l <= r && que[l] < max(1ll, j-d*(t[i]-t[i-1])) ) l++;
            f[fl][j] = f[fl^1][que[l]] - abs(a[i]-j) + b[i];
        }

        fl ^= 1;
    }
}

int main() {
    freopen("input.txt", "r", stdin);
    cin >> n >> m >> d;
    _rep(i, 1, m) {
        cin >> a[i] >> b[i] >> t[i];
        //debug(t[i]);
    }

    // then dp
    dp();
    ll ans = inf;
    _rep(i, 1, n) chmax(ans, f[fl^1][i]);
    cout << ans << endl;
}