APIO2020 粉刷墙壁

考场想了 5.5 h，第一部分分死活打不出来，做到崩盘，现在重做，感觉自己就是一个sb，放学在地铁上一眼就会了。哎。

可以把一个要求看作一个长度为 $m$ 的区间：$[l, l + m - 1]$，可以要求这段条件的充要条件是找到一种循环移位，每个墙恰好可以被那个工人挖。然后问题是用最少的区间覆盖完 $[0, n - 1]$。

可以设一个 DP：

$f_i $：刷完前 $i$ 个墙的最小要求次数。

如果 $[i - m + 1, i]$ 可以刷，那么 $f_i = \min_{i-m\le j <i}(f_j) + 1$。
否则 $f_i$ 是正无穷。

这个东西显然是一个滑动窗口最值，用单调队列优化，我们现在的就要求快速判断 $[i - m + 1, i]$ 能不能刷。

设 $len_{i, j}$ 为第 $i$ 个墙，第 $j$ 个人刷，最多可以循环移位向前延伸多少个。

对于一个 $i$，枚举 $C_i$ 颜色对应的所有的工人 $u$，转移 $len_{i, u} = len_{i - 1, (u - 1) \bmod m} + 1$。

由于 $\sum f(k)^2 \le 400000$，所以 $f(k)$ 是 $600$ 量级的，时间复杂度是 $O(n \max(f(k)))$ 是可以过的。

但是空间不够，滚动数组就好了，但是还要保证转移的是 $i - 1$ 次，所以每次转移赋值 $g_{i \bmod 2, j} = i$，表示这个循环移位最后的位置是 $i$。转移判断上次的是不是 $i - 1$ 就行了。

单调队列还有一些细节，比如正无穷不能扔进队列之类。

#include <vector>

#include <cstring>

#include <iostream>

using namespace std;

const int N = 100005, M = 50005, INF = 0x3f3f3f3f;

int f[N], q[N], g[2][M], len[2][M];

vector<int> d[N];

int minimumInstructions(

    int n, int m, int K, std::vector<int> c,

    std::vector<int> a, std::vector<std::vector<int> > b) {

  	memset(f, 0x3f, sizeof f);

  	memset(g, -1, sizeof g);

  	for (int i = 0; i < K; i++) d[i].clear();

  	for (int i = 0; i < m; i++) {

  		for (int j = 0; j < a[i]; j++) {

  			d[b[i][j]].push_back(i);

  		}

  	}

  	int hh = 0, tt = -1;

  	for (int i = 0; i < n; i++) {

  		bool ok = false;

  		for (int j = 0; j < d[c[i]].size(); j++) {

  			int u = d[c[i]][j];

  			g[i & 1][u] = i, len[i & 1][u] = 1;

  			if (i && g[(i - 1) & 1][(u + m - 1) % m] == i - 1) len[i & 1][u] += len[(i - 1) & 1][(u + m - 1) % m];

  			if (len[i & 1][u] >= m) ok = true;

  		}

  		if (ok) {

  			while (hh <= tt && q[hh] < i - m) hh++;

  			if (i < m) f[i] = 1;

  			else if (hh <= tt) f[i] = f[q[hh]] + 1;

  			if (f[i] != INF) {

  				while (hh <= tt && f[q[tt]] >= f[i]) tt--;

                                q[++tt] = i;

  			}

  		}

  	}

  	return f[n - 1] == INF ? -1 : f[n - 1];

}

巴特西

APIO2020 粉刷墙壁

最新文章

热门文章