【矩阵DP + 线段树】The 2019 Asia Nanchang First Round Online Programming Contest - C - Hello 2019

题目链接

题意

给出一串数字，有Q个询问，每次询问一个区间，问删除最少几个字符使得区间内包含子序列9102但不包含子序列8102。

题解

首先将整个串倒过来。
如果不考虑区间，那么一个普通的$dp$就行了。$dp[i][j]$表示第$i$位数字，当前匹配了2019的第$j$位。转移方程分六种情况，比如当前位是2，转移方程就是$dp[i][1]=min(dp[i-1][1],dp[i-1][0]+1)$。

这题因为询问的是区间，所以要把$dp$用矩阵表示，并用线段树维护子区间的矩阵乘法，矩阵乘法就用刚才的转移方程表示即可。如果仔细推一下，此时的转移方程还是满足矩阵乘法的性质的。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double db;
const int N=2e5+7;
const int inf=1e8+7;
int n,q;
char s[N];
struct Matrix{
    int mat[5][5];
    void init(){
        for(int i=0;i<5;i++){
            for(int j=0;j<5;j++){
                if(i==j) mat[i][j]=0;
                else mat[i][j]=inf;
            }
        }
    }

}t[N<<2];
Matrix mul(Matrix a,Matrix b){
    Matrix c;
    for(int i=0;i<5;i++){
        for(int j=0;j<5;j++){
            c.mat[i][j]=inf;
            for(int k=0;k<5;k++){
                c.mat[i][j]=min(c.mat[i][j],a.mat[i][k]+b.mat[k][j]);
            }
        }
    }
    return c;
}
void bd(int rt,int l,int r){
    if(l==r){
        t[rt].init();
        if(s[l]=='2') t[rt].mat[0][0]=1,t[rt].mat[0][1]=0;
        if(s[l]=='0') t[rt].mat[1][1]=1,t[rt].mat[1][2]=0;
        if(s[l]=='1') t[rt].mat[2][2]=1,t[rt].mat[2][3]=0;
        if(s[l]=='9') t[rt].mat[3][3]=1,t[rt].mat[3][4]=0;
        if(s[l]=='8') t[rt].mat[3][3]=1,t[rt].mat[4][4]=1;
        return;
    }
    int m=l+r>>1;
    bd(rt<<1,l,m);
    bd(rt<<1|1,m+1,r);
    t[rt]=mul(t[rt<<1],t[rt<<1|1]);
}
Matrix que(int rt,int l,int r,int L,int R){
    if(L<=l&&r<=R) return t[rt];
    int m=l+r>>1;
    Matrix le,ri;le.init();ri.init();
    if(L<=m) le=que(rt<<1,l,m,L,R);
    if(m<R) ri=que(rt<<1|1,m+1,r,L,R);
    return mul(le,ri);
}
int main()
{
    scanf("%d%d%s",&n,&q,s);
    int sz=strlen(s);
    reverse(s,s+sz);
    bd(1,0,sz-1);
    for(int i=1,l,r;i<=q;i++){
        scanf("%d%d",&l,&r);
        r=sz-r;l=sz-l;
        swap(l,r);
        Matrix ans=que(1,0,sz-1,l,r);
        if(ans.mat[0][4]==inf) printf("-1\n");
        else printf("%d\n",ans.mat[0][4]);
    }
}