动态规划综合(六)

这篇博文探讨了单调队列优化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
将区间 [l, r] 划分成为 [l, mid] 和 [mid+1, r]
更新操作是 r = mid 或者 l = mid + 1
最后的答案是新区间的 l

int bsearch(int l, int r) {
while (l < r) {
int mid = l + r >> 1;
if (check(mid)) r = mid;
else l = mid + 1;
}
return l;
}
1
2
3
4
5
6
7
8
9
10
11
12
将区间 [l, r] 划分成为 [l, mid-1] 和 [mid, r]
更新操作是 l = mid 或者是 r = mid - 1
为了防止死循环,计算 mid = l + r + 1 >> 1;

int bsearch(int l, int r) {
while (l < r) {
int mid = l + r + 1 >> 1;
if (check(mid)) l = mid;
else r = mid - 1;
}
return l;
}

两种二分,实际上是上取整和下取整的不同
实际上,中点都满足 $mid = (l+r) / 2$

第一种情况
$[l,r] \to [l,mid] \cup [mid+1, r]$

第二种情况
$[l,r] \to [l,mid-1] \cup [mid, r]$
边界条件是 $r = l+1$
此时 $mid = (2l+1)/2 = l$ 恒成立
$[l, r] \to [mid, r]=[l,r]$
区间没有发生变化,导致死循环
解决方法是 $mid = (l+r+1) / 2$ 进行上取整即可

滑动窗口与单调队列

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

滑动窗口

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;
}