Description
A string t is called nice if a string "2017" occurs in t as a subsequence but a string "2016" doesn't occur in t as a subsequence. For example, strings "203434107" and "9220617" are nice, while strings "20016", "1234" and "20167" aren't nice.
The ugliness of a string is the minimum possible number of characters to remove, in order to obtain a nice string. If it's impossible to make a string nice by removing characters, its ugliness is - 1.
Limak has a string s of length n, with characters indexed 1 through n. He asks you q queries. In the i-th query you should compute and print the ugliness of a substring (continuous subsequence) of s starting at the index ai and ending at the index bi (inclusive).
Solution
考虑朴素DP,记录\(2\),\(20\),\(201\),\(2017\)之间相互转移的最小代价,复杂度 \(O(N*Q)\)
这个过程可以矩乘优化,\(a[i][j]\)表示状态 \(i\) 转移到 状态\(j\)的代价,线段树维护区间答案即可
#include <bits/stdc++.h>
#define ls (o<<1)
#define rs (o<<1|1)
using namespace std;
const int N=200005,inf=2e8;
int n,Q;char s[N];
struct node{
int a[5][5];
node(){memset(a,0,sizeof(a));}
node operator *(const node &p){
node ret;
for(int i=0;i<5;i++)
for(int j=0;j<5;j++){
ret.a[i][j]=inf;
for(int k=0;k<5;k++)
ret.a[i][j]=min(ret.a[i][j],a[i][k]+p.a[k][j]);
}
return ret;
}
}tr[N<<2];
inline void build(int l,int r,int o){
if(l==r){
for(int i=0;i<5;i++)
for(int j=0;j<5;j++)
tr[o].a[i][j]=(i==j?0:inf);
if(s[l]=='2')tr[o].a[0][0]=1,tr[o].a[0][1]=0;
else if(s[l]=='0')tr[o].a[1][1]=1,tr[o].a[1][2]=0;
else if(s[l]=='1')tr[o].a[2][2]=1,tr[o].a[2][3]=0;
else if(s[l]=='7')tr[o].a[3][3]=1,tr[o].a[3][4]=0;
else if(s[l]=='6')tr[o].a[4][4]=1,tr[o].a[3][3]=1;
return ;
}
int mid=(l+r)>>1;
build(l,mid,ls);build(mid+1,r,rs);
tr[o]=tr[ls]*tr[rs];
}
inline node qry(int l,int r,int o,int sa,int se){
if(sa<=l && r<=se)return tr[o];
int mid=(l+r)>>1;
if(se<=mid)return qry(l,mid,ls,sa,se);
else if(sa>mid)return qry(mid+1,r,rs,sa,se);
else return qry(l,mid,ls,sa,mid)*qry(mid+1,r,rs,mid+1,se);
}
int main()
{
freopen("pp.in","r",stdin);
freopen("pp.out","w",stdout);
scanf("%d%d%s",&n,&Q,s+1);
build(1,n,1);
while(Q--){
int x,y;node t;
scanf("%d%d",&x,&y);
t=qry(1,n,1,x,y);
if(t.a[0][4]==inf)puts("-1");
else printf("%d\n",t.a[0][4]);
}
return 0;
}