思路：
本质上能进行的操作就是我们算出从第 \(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();}