题：https://nanti.jisuanke.com/t/41350

分析：先将字符串转置过来

状态转移，因为只有5个状态，所以 i 状态到 j 状态的最小代价就枚举【i】【k】->【k】【j】的最小值（0<=k<=4）

0：初始状态

1：2

2：20

3：201

4：2019

mat[i][j]表示状态i转移到j的最小代价

#include
       
        using namespace std;#define lson root<<1,l,midd#define rson root<<1|1,midd+1,rconst int N=2e5+5;struct node{    int mat[5][5];    void init(){        memset(mat,0x3f,sizeof(mat));    }    node operator + (const node &b){        node ret;        for(int i=0;i<5;i++)            for(int j=0;j<5;j++){                ret.mat[i][j]=N;                for(int k=0;k<5;k++)                    ret.mat[i][j]=min(ret.mat[i][j],mat[i][k]+b.mat[k][j]);            }        return ret;    }}tree[N<<2],ANS;char s[N];void build(int root,int l,int r){    if(l==r){        for(int i=0;i<5;i++)            for(int j=0;j<5;j++)                if(j!=i)                    tree[root].mat[i][j]=N;                else                    tree[root].mat[i][j]=0;        if(s[l]=='8')            tree[root].mat[4][4]=1,tree[root].mat[3][3]=1;        else if(s[l]=='9')            tree[root].mat[3][3]=1,tree[root].mat[3][4]=0;        else if(s[l]=='1')            tree[root].mat[2][2]=1,tree[root].mat[2][3]=0;        else if(s[l]=='0')            tree[root].mat[1][1]=1,tree[root].mat[1][2]=0;        else if(s[l]=='2')            tree[root].mat[0][0]=1,tree[root].mat[0][1]=0;        return ;    }    int midd=(l+r)>>1;    build(lson);    build(rson);    tree[root]=tree[root<<1]+tree[root<<1|1];}void query(int L,int R,int root,int l,int r){    if(L<=l&&r<=R){        ANS=ANS+tree[root];        return ;    }    int midd=(l+r)>>1;    if(L<=midd)        query(L,R,lson);    if(R>midd)        query(L,R,rson);    }char f[N];int main(){    int n,t;    scanf("%d%d",&n,&t);    scanf("%s",f+1);    for(int i=1,j=n;i<=n;i++,j--)        s[i]=f[j];    //cout<