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).
题面
考虑朴素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; }转载于:https://www.cnblogs.com/Yuzao/p/8423934.html
相关资源：数据结构—成绩单生成器