P6764 [APIO2020] 粉刷墙壁-数字星空

思路：

本质上能进行的操作就是我们算出从第 $i$ 块砖开始，连续刷 $M$ 块砖，是否有承包商可以刷出期望颜色。

那么设 $f_i$ 表示 $[i,i+m-1]$ 是否合法，那么就变成了最小区间覆盖问题。

最小区间覆盖问题

令 $Max$ 表示当前覆盖了 $[1,Max]$。

那么我们需要找到左端点在 $[1,Max+1]$ 内，且右端点最大的区间。

在本题中因为区间长度都为 $m$，那么我们只需要找到尽可能在最后的合法 $f_i$。

此时 $Max \gets i+m-1$，那么对于小于 $j$ 的 $i$，是无法覆盖到 $i+m-1$ 之后的，于是就没有贡献了，于是我们可以直接走指针维护。

最小区间覆盖代码

ll get(){
	ll Max=-1,x=0,id,ans=0;
	while(Max<n-1){
		id=-1;
		while(x<=Max+1&&x<n){
			if(f[x])
			  id=x;
			x++;
		}
		if(id==-1)
		  return -1;
		Max=id+m-1;
		ans++;
	}
	return ans;
}

那么我们需要考虑的就是如何求出 $f_i$。

28pts：

对于每个 $i$，暴力枚举一个 $j$，然后查看是否能匹配上。

时间复杂度为 $O(NM^2)$。

51pts：

考虑动态规划优化，定义 $dp_{i,j}$ 表示从第 $i$ 块墙壁开始，从第 $j$ 个商家开刷最多能刷几块墙。

那么若第 $j$ 个商家不能刷第 $i$ 个墙壁，则：

\[dp_{i,j}=0 \]

否则能刷：

\[dp_{i,j} = dp_{i+1,(j+1) \bmod M} + 1 \]

注意，空间开不下，考虑滚动数组优化。

时间复杂度为 $O(NM)$。

~~震惊的是，这玩意儿竟然过了……~~

离大谱。

$O(NM)$ 代码

int minimumInstructions(int N, int M, int K,vector<int> C,vector<int> A,vector<vector<int>> B){
	n=N,m=M,k=K;
	for(int i=0;i<n;i++)
	  a[i]=C[i];
	for(int i=0;i<m;i++){
		len[i]=A[i];
		for(auto v:B[i])
		  s[v].push_back(i);
	}
	for(int i=n-1;i>=0;i--){
		for(int j=0;j<m;j++)
		  dp[i&1ll][j]=0;
		for(auto j:s[a[i]]){
			dp[i&1ll][j]=dp[(i&1ll)^1ll][(j+1)%m]+1;
			if(dp[i&1ll][j]>=m)
			  f[i]=1;
		}
	}
	cerr<<'\n'<<abs(&Begin-&End)/1048576<<"MB"<<'\n';
	return get();
}

100pts：

注意到可以优化上面状态转移的 $j$。

我们可以提前预处理能刷颜色 $x$ 的承包商的集合 $S_x$，那么 $j \in S_{c_i}$。

但是因为是滚动数组，实时清空的话复杂度又上去了，那么再维护一个时间戳即可。

时间复杂度为 $O(\sum f(k))$。

完整代码：

#include<bits/stdc++.h>
#define Add(x,y) (x+y>=mod)?(x+y-mod):(x+y)
#define lowbit(x) x&(-x)
#define pi pair<ll,ll>
#define pii pair<ll,pair<ll,ll>>
#define iip pair<pair<ll,ll>,ll>
#define ppii pair<pair<ll,ll>,pair<ll,ll>>
#define fi first
#define se second
#define full(l,r,x) for(auto it=l;it!=r;it++) (*it)=x
#define Full(a) memset(a,0,sizeof(a))
#define open(s1,s2) freopen(s1,"r",stdin),freopen(s2,"w",stdout);
using namespace std;
typedef double db;
typedef unsigned long long ull;
typedef int ll;
bool Begin;
const ll N=100100,M=50050;
inline ll read(){
    ll x=0,f=1;
    char c=getchar();
    while(c<'0'||c>'9'){
        if(c=='-')
          f=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9'){
        x=(x<<1)+(x<<3)+(c^48);
        c=getchar();
    }
    return x*f;
}
inline void write(ll x){
	if(x<0){
		putchar('-');
		x=-x;
	}
	if(x>9)
	  write(x/10);
	putchar(x%10+'0');
}
ll n,m,k;
ll a[N],len[M];
ll dp[2][M],low[2][M];
vector<ll> s[N];
bool f[N];
bool End;
ll get(){
	ll Max=-1,x=0,id,ans=0;
	while(Max<n-1){
		id=-1;
		while(x<=Max+1&&x<n){
			if(f[x])
			  id=x;
			x++;
		}
		if(id==-1)
		  return -1;
		Max=id+m-1;
		ans++;
	}
	return ans;
}
int minimumInstructions(int N, int M, int K,vector<int> C,vector<int> A,vector<vector<int>> B){
	n=N,m=M,k=K;
	for(int i=0;i<n;i++)
	  a[i]=C[i];
	for(int i=0;i<m;i++){
		len[i]=A[i];
		for(auto v:B[i])
		  s[v].push_back(i);
	}
	for(int i=n-1;i>=0;i--){
		for(auto j:s[a[i]]){
			if(low[(i&1ll)^1ll][(j+1)%m]!=i+1)
			  dp[i&1ll][j]=1;
			else
			  dp[i&1ll][j]=dp[(i&1ll)^1ll][(j+1)%m]+1;
			low[i&1ll][j]=i;
			if(dp[i&1ll][j]>=m)
			  f[i]=1;
		}
	}
	cerr<<'\n'<<abs(&Begin-&End)/1048576<<"MB"<<'\n';
	return get();
}