眼科医院网站开发,花生壳 建设网站,国内最炫酷的网站,模板网站建设+百度正题
题目链接:https://www.luogu.com.cn/problem/CF750E 题目大意
给出一个长度为nnn的数字字符串#xff0c;qqq次询问给出其的一个子串ttt#xff0c;询问至少要删除多少个数字才能使得其中包含201720172017这个子序列却不包含201620162016这个子序列。 1≤n,q≤21051\l…正题
题目链接:https://www.luogu.com.cn/problem/CF750E 题目大意
给出一个长度为nnn的数字字符串qqq次询问给出其的一个子串ttt询问至少要删除多少个数字才能使得其中包含201720172017这个子序列却不包含201620162016这个子序列。
1≤n,q≤2×1051\leq n,q\leq 2\times 10^51≤n,q≤2×105 解题思路
写点水题复复健。
直接上动态dpdpdp设fif_ifi表示目前匹配到201720172017的第iii个需要的最小代价。
然后匹配到111之后遇到的666一定要删除就好了。
时间复杂度O(53nlogn)O(5^3n\log n)O(53nlogn) code
#includecstdio
#includecstring
#includealgorithm
using namespace std;
const int N2e510,MN2,S5;
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 i0;iS;i)for(int j0;jS;j)for(int k0;kS;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(LR){w[x]mx[s[L]-0];return;}int mid(LR)1;Build(x*2,L,mid);Build(x*21,mid1,R);w[x]w[x*2]*w[x*21];return;
}
Matrix Ask(int x,int L,int R,int l,int r){if(LlRr){return w[x];}int mid(LR)1;if(rmid)return Ask(x*2,L,mid,l,r);if(lmid)return Ask(x*21,mid1,R,l,r);return Ask(x*2,L,mid,l,mid)*Ask(x*21,mid1,R,mid1,r);
}
int main()
{for(int i0;iM;i)memset(w[i].a,0x3f,sizeof(w[i].a));for(int i0;i10;i){memset(f.a,0x3f,sizeof(f.a));for(int j0;jS;j)f.a[j][j]0;if(i2)f.a[0][1]0,f.a[0][0]1;else if(i0)f.a[1][2]0,f.a[1][1]1;else if(i1)f.a[2][3]0,f.a[2][2]1;else if(i7)f.a[3][4]0,f.a[3][3]1;else if(i6)f.a[3][3]f.a[4][4]1;mx[i]f;}scanf(%d%d,n,q);scanf(%s,s1);Build(1,1,n);while(q--){int l,r;scanf(%d%d,l,r);fAsk(1,1,n,l,r);int ansf.a[0][4];if(ans2147483647/3)puts(-1);else printf(%d\n,ans);}return 0;
}
