关于天数限制的动态规划的一类常见技巧

例题：P6647 [CCC2019] Tourism

题目大意：

给定 \(n\) 个景点，每天可以游览至多 \(k\) 个景点，满足用 \(t\) 天浏览，\(t\) 必须最小，能得到的最大评分是多少？

解决方法：

首先不考虑天数限制，考虑动态规划

明显的，设 \(f_i\) 为前 \(i\) 天所能获得的最大评分，一天可以从 \([i-k,i)\) 转移，容易写出状态转移方程：

但是加上天数限制怎么做？

天数最少是不是说明转移次数越少？

那现在每次转移的代价都是一样的，如果我们给每次转移加上一个代价，是不是就可以让 \(f\) 迫不得已选择转移次数少的那个？

那怎么给每个转移加上一个代价呢？

我们是不是只要在转移后面加上一个 \(-\infty\)，转移次数越多积累的 \(-\infty\) 越多，是不是就越小？

于是，我们更改状态转移方程，为了更加直观，我们定义 \(Sum(i,j)=\max_{i\le k \le j}\{A_k\}\)，则状态转移方程如下：

直接暴力的话时间复杂度为 \(O(n^3)\)，肯定不行

我们考虑优化转移过程

当我看到 \(i-k\le j<i\) 了，迅速想到了单调队列，但真的可以吗？

我们可以看到 \(Sum(j+1,i)\) 是个定值吗？很明显并不是，所以里面的式子他是在一直变化的，这让我们想到了具有 动态修改功能的线段树可以 \(\log\) 级维护

那变化的值呢？

很明显，如果一个 \(i\) 进来，那么所有比他小的数 \(j\) 都要增加 \(A_i-A_j\) 这个值，什么东西能维护这个东西呢？

能想到用单调栈，如果一个数 \(j\) 被 \(i\) 弹出，那么什么区间会被影响到呢？

自行模拟一下，可以发现 \([T_{top-1},T_{top}-1]\) 这个区间被影响了，区间操作即可

最后把 \(f_{i-1}+A_i\) 这个值进行单修，最后区查即可

Qestion

那如果被 \(j\) 弹掉的 \(k\) 呢？它的大小似乎没有更新

Answer

由于在 \(k\) 的值是小于等于在 \(j\) 的值的，当且仅当在 \(k\) 更新 \(j\) 时取等，这等同于加 \(j\)，并没有影响（毕竟是最大值嘛

最后献上代码

#include <bits/stdc++.h>

using namespace std;

const int MAXN = 1e6 + 7;

typedef long long ll;

const ll Inf = 1e12;

struct Segt_Tree{//需要实现区查区改单改 
	struct Node {ll sum, lz; }t[4 * MAXN];
	#define ls(i) (i << 1)
	#define rs(i) (i << 1 | 1)
	
	void push_up(int cur) {t[cur].sum = max(t[ls(cur)].sum, t[rs(cur)].sum); }
	void f(int cur, int l, int r, ll k) {
		t[cur].sum += k;
		t[cur].lz += k;
	}
	void push_down(int cur, int l, int r) {
		int mid = l + r >> 1;
		f(ls(cur), l, mid, t[cur].lz); f(rs(cur), mid + 1, r, t[cur].lz);
		t[cur].lz = 0;
	}
	
	void modify_qj(int cur, int l, int r, int x, int y, ll k) {
		if (x <= l && y >= r) {
			f(cur, l, r, k); return ;
		}
		int mid = l + r >> 1; push_down(cur, l, r);
		if (x <= mid) modify_qj(ls(cur), l, mid, x, y, k);
		if (y > mid ) modify_qj(rs(cur), mid + 1, r, x, y, k);
		push_up(cur);	
	}
	void modify_dd(int cur, int l, int r, int x, ll k) {
		if (l == r) {
			f(cur, l, r, k); return ;
		}	
		int mid = l + r >> 1; push_down(cur, l, r);
		if (x <= mid) modify_dd(ls(cur), l, mid, x, k);
		else modify_dd(rs(cur), mid + 1, r, x, k);
		push_up(cur);
	}
	ll query(int cur, int l, int r, int x, int y) {
		if (x <= l && y >= r) return t[cur].sum;
		int mid = l + r >> 1; ll ans = -1e18; push_down(cur, l, r);
		if (x <= mid) ans = max(ans, query(ls(cur), l, mid, x, y));
		if (y > mid ) ans = max(ans, query(rs(cur), mid + 1, r, x, y));
		return ans; 
	}
}t;

int n, k, A[MAXN];

int T[MAXN], tp;

ll F[MAXN];

// f[i]= max{f[j] + g(j+1, i)} - inf

int main () {
	cin >> n >> k;	
	for (int i = 1; i <= n; i ++) cin >> A[i];
	for (int i = 1; i <= n; i ++) {
		while (tp && A[T[tp]] <= A[i]) {
			t.modify_qj(1, 0, n, T[tp - 1], T[tp] - 1, A[i] - A[T[tp]]);
			tp --;
		}
		T[++ tp] = i;
		t.modify_dd(1, 0, n, i - 1, F[i - 1] + A[i]);
		F[i] = t.query(1, 0, n, max(i - k, 0), i - 1) - Inf;
		
	}
	cout << F[n] + ((n - 1) / k + 1) * Inf << '\n';
	return 0;
}

积累到一个 trick好叭（很开心

完结撒花✿✿ヽ(°▽°)ノ✿