重学单调队列优化dp

再谈单调队列优化dp。

题目：CF1077F1&2 Pictures with Kittens(Easy & hard version)

从n个数中选出m个数，连续k个数至少选出一个，最大化选出数和。

easy version普通dp，hard则需要单调队列优化。

借此机会我也深入体会了一下dp逻辑。

与此题很相似的有一道USACO的题，也是单调队列优化dp，是从n个数中选数，不能选超过连续k个数，最大化选数和（状态 \(f_{i,0|1}\) 表示第 \(i\) 个选或不选）。

设 \(f_{i,j}\) 为前 \(i\) 个数中选 \(j\) 个数，第 \(i\) 个数必选的最大和。

方程：\(f_{i,j} = \max\limits^{i-1}_{p=\max(0,i-k)}f_{p,j-1} + a_i\)

这里有个细节，如果 \(i<k\) 为什么 \(p\) 要从 \(0\) 开始？参考关于dp方程的一个小问题

也可以从 \(1\) 开始。不过要把 \(f_{i,1}\ i<=k\) 赋为 \(a_i\)。我们把 \(f_{0,0}\) 理解为不选，\(p=0\) 开始意味着在 \(j = 1\) 的时候要从不选中转移出初始化的数据。从 \(1\) 开始就需要先前赋值。

还有，\(f\) 数组要初始化为 \(-inf\)，不知为何。

总结：做dp题总是会有很多思维误区，比如 \(i>k\) 时 \(f_{i,1}\ne a_i\) 等。平日练习一定要理解透彻，深入总结。同时，dp过程如果不清晰的话，可以画个DAG理解。

#include <bits/stdc++.h>
#define ll long long
using namespace std;
ll a[5005];
int n, m, k;
ll f[5005][5005];
int main()
{
    ios::sync_with_stdio(false);
    memset(f, 0xcf, sizeof(f));
    cin >> n >> k >> m;
    if (n / k > m) {
        cout << -1 << endl;
        return 0;
    }
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        if(i <= k) f[i][1] = a[i];
    }
    for (int j = 1; j <= m; j++) {
        for (int i = 1; i <= n; i++) {
            if (j > i) continue;
            for (int p = max(1, i - k); p < i; p++) {
                f[i][j] = max(f[i][j], f[p][j - 1] + a[i]);
            }
        }
    }
    ll ans = 0;
    for (int i = n - k + 1; i <= n; i++) {
        ans = max(ans, f[i][m]);
    }
    cout << ans << endl;
    return 0;
}

下一步是F2，考虑优化求最大值，一种方法是ST表，一种方法是单调队列。

这道题ST表理论上可以过，但是咕咕了。

下面是单调队列的。

单调队列维护 \(f_{i,j-1}, 1 \le i \le n\) 的max

#include <bits/stdc++.h>
#define ll long long
using namespace std;
ll a[5005];
int n, m, k;
ll f[5005][5005];
deque<pair<int, ll> >q;
int main()
{
	ios::sync_with_stdio(false);
	memset(f, 0xcf, sizeof(f));
	f[0][0] = 0;
	cin >> n >> k >> m;
	if (n / k > m) {
		cout << -1 << endl;
		return 0;
	}
	for (int i = 1; i <= n; i++) {
		cin >> a[i];
		if (i <= k) f[i][1] = a[i];
	}
	for (int j = 1; j <= m; j++) {
		q.clear();
		for (int i = 1; i <= n; i++) {
			while (q.size() && q.front().first + k < i) q.pop_front();
			if (q.size()) f[i][j] = max(f[i][j], q.front().second + a[i]);
			while (q.size() && q.back().second <= f[i][j - 1]) q.pop_back();
			q.push_back(make_pair(i, f[i][j - 1]));
		}
	}
	ll ans = 0;
	for (int i = n - k + 1; i <= n; i++) {
		ans = max(ans, f[i][m]);
	}
	cout << ans << endl;
	return 0;
}