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;

}