正题

题目链接:https://www.luogu.com.cn/problem/CF750E

---

题目大意

给出一个长度为$n$的数字字符串，$q$次询问给出其的一个子串$t$，询问至少要删除多少个数字才能使得其中包含$2017$这个子序列却不包含$2016$这个子序列。

$1\le n,q\le 2\times 10^5$

---

解题思路

写点水题复复健。

直接上动态$dp$，设$f_i$表示目前匹配到$2017$的第$i$个需要的最小代价。

然后匹配到$1$之后遇到的$6$一定要删除就好了。

时间复杂度：$O(5^{3}n\log n)$

---

code

#include<cstdio> #include<cstring> #include<algorithm> using namespace std; const int N=2e5+10,M=N<<2,S=5; int n,q;char s[N]; struct Matrix{int a[S][S]; }c,f,mx[10],w[M]; Matrix operator*(Matrix a,Matrix b){memset(c.a,0x3f,sizeof(c.a));for(int i=0;i<S;i++)for(int j=0;j<S;j++)for(int k=0;k<S;k++)c.a[i][j]=min(c.a[i][j],a.a[i][k]+b.a[k][j]);return c; } void Build(int x,int L,int R){if(L==R){w[x]=mx[s[L]-'0'];return;}int mid=(L+R)>>1;Build(x*2,L,mid);Build(x*2+1,mid+1,R);w[x]=w[x*2]*w[x*2+1];return; } Matrix Ask(int x,int L,int R,int l,int r){if(L==l&&R==r){return w[x];}int mid=(L+R)>>1;if(r<=mid)return Ask(x*2,L,mid,l,r);if(l>mid)return Ask(x*2+1,mid+1,R,l,r);return Ask(x*2,L,mid,l,mid)*Ask(x*2+1,mid+1,R,mid+1,r); } int main() {for(int i=0;i<M;i++)memset(w[i].a,0x3f,sizeof(w[i].a));for(int i=0;i<10;i++){memset(f.a,0x3f,sizeof(f.a));for(int j=0;j<S;j++)f.a[j][j]=0;if(i==2)f.a[0][1]=0,f.a[0][0]=1;else if(i==0)f.a[1][2]=0,f.a[1][1]=1;else if(i==1)f.a[2][3]=0,f.a[2][2]=1;else if(i==7)f.a[3][4]=0,f.a[3][3]=1;else if(i==6)f.a[3][3]=f.a[4][4]=1;mx[i]=f;}scanf("%d%d",&n,&q);scanf("%s",s+1);Build(1,1,n);while(q--){int l,r;scanf("%d%d",&l,&r);f=Ask(1,1,n,l,r);int ans=f.a[0][4];if(ans>=2147483647/3)puts("-1");else printf("%d\n",ans);}return 0; }

总结

以上是生活随笔为你收集整理的CF750E-New Year and Old Subsequence【动态dp】的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。