The 2019 Asia Nanchang First Round Online Programming Contest C. Hello 2019 —— 线段树上DP

This way

题意：

给你n个数，每次问你l到r区间中至少要去掉几个数使得剩下的数中含有9102序列而没有8102序列

题解：

第一次见到这种题，涨见识了。
它好像和CF的一道题目基本差不多：This way
这道题是判9102与8102，如果从左往右的话会多出很多状态，不如将其反一下，变成2018与2019，这样的话就记录
空状态为0
2为1,20为2，201为3，2019为4
那么重载一下运算符即可，其实就是状态转移
在当前字符为8的时候m[3][3]=m[4][4]=1表示有201或者2019两个状态的时候有8出现那么就是不合法，需要将一个数删掉

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+5;
struct Matrice
{
int m[5][5];
void init(){memset(m,0x3f3f3f,sizeof(m));}
Matrice operator* (const Matrice& a)const
{
Matrice ans;
ans.init();
for(int k=0;k<5;k++)
for(int i=0;i<5;i++)
for(int j=0;j<5;j++)
ans.m[i][j]=min(ans.m[i][j],m[i][k]+a.m[k][j]);
return ans;
}
}mi[N*4],aa;
int a[N];
void cal(int x,int root)
{
mi[root].init();
for(int i=0;i<5;i++)mi[root].m[i][i]=0;
if(a[x]==2)mi[root].m[0][0]=1,mi[root].m[0][1]=0;
if(a[x]==0)mi[root].m[1][1]=1,mi[root].m[1][2]=0;
if(a[x]==1)mi[root].m[2][2]=1,mi[root].m[2][3]=0;
if(a[x]==9)mi[root].m[3][3]=1,mi[root].m[3][4]=0;
if(a[x]==8)mi[root].m[3][3]=mi[root].m[4][4]=1;
}
void build(int l,int r,int root)
{
if(l==r)
{
cal(l,root);
return ;
}
int mid=l+r>>1;
build(l,mid,root<<1);
build(mid+1,r,root<<1|1);
mi[root]=mi[root<<1]*mi[root<<1|1];
}
void query(int l,int r,int root,int ql,int qr)
{
if(l>=ql&&r<=qr)
{
aa=aa*mi[root];
return ;
}
int mid=l+r>>1;
int ans=N;
if(mid>=ql)
query(l,mid,root<<1,ql,qr);
if(mid<qr)
query(mid+1,r,root<<1|1,ql,qr);
}
int main()
{
int n,m;
scanf("%d%d",&n,&m);
for(int i=n;i>=1;i--)scanf("%1d",&a[i]);
build(1,n,1);
int l,r;
for(int i=1;i<=m;i++)
{
scanf("%d%d",&l,&r);
aa.init();
for(int i=0;i<5;i++)
for(int j=0;j<5;j++)
aa.m[i][i]=0;
l=n-l+1,r=n-r+1;
query(1,n,1,r,l);
printf("%dn",aa.m[0][4]<=n?aa.m[0][4]:-1);
}
return 0;
}

最后

以上就是可耐刺猬为你收集整理的The 2019 Asia Nanchang First Round Online Programming Contest C. Hello 2019 —— 线段树上DP的全部内容，希望文章能够帮你解决The 2019 Asia Nanchang First Round Online Programming Contest C. Hello 2019 —— 线段树上DP所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。