Thoughts:
Essentially the operation that can be performed is that we count the number of steps from the first\(i\) Starting with a brick, successive swipes\(M\) brick, is there a contractor who can paint the desired color.
in that case\(f_i\) indicate\([i,i+m-1]\) whether it is legal or not, then it becomes a minimum interval coverage problem.
Minimum Interval Coverage Problem
honorific title\(Max\) Indicates that the current override\([1,Max]\)。
Then we need to find the left endpoint in\([1,Max+1]\) within the interval with the largest right endpoint.
In this question because the intervals are all of length\(m\)Then we just need to find as much as possible at the end of the legal\(f_i\)。
this time\(Max \gets i+m-1\), then for a number less than\(j\) (used form a nominal expression)\(i\), is unable to cover the\(i+m-1\) After that, so there's no contribution, and so we can just go pointer maintenance.
Minimum interval coverage code
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;
}
Then all we need to consider is how to find the\(f_i\)。
28pts：
For each\(i\)The violent enumeration of a\(j\), and then check to see if it matches.
The time complexity is\(O(NM^2)\)。
51pts：
Consider dynamic programming optimization and define\(dp_{i,j}\) Indicates a change from the first (i.e., from the first) to the second (ii).\(i\) Starting with the first block of wall, from the first\(j\) The maximum number of walls that can be painted by a single merchant open brush.
Then if the first\(j\) A merchant cannot swipe the first\(i\) A wall, then:
Otherwise it can be brushed:
Note that space is not open enough to consider rolling array optimization.
The time complexity is\(O(NM)\)。
Shocked that this stuff is over ......
Off the big spectrum.
$O(NM)$ Code
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：
Notice that it is possible to optimize the above state transfer\(j\)。
We can pre-process in advance to be able to paint colors\(x\) the collection of contractors of the\(S_x\)So.\(j \in S_{c_i}\)。
But because it's a rolling array, the complexity goes up again if it's emptied in real time, so just maintain another timestamp.
The time complexity is\(O(\sum f(k))\)。
Full Code:
#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();
}