bzoj 4521: [Cqoi2016]手机号码

.

题意：l~r中有多少个符合要求的数。要求：号码中要出现至少3个相邻的相同数字，号码中不能同时出现8和4。
题解：数位DP
$f[i][j][k][l][o][p]$表示前i个位置是j，有连续k个j，l表示是否满足了连续3个的条件，o表示4和8的状态，0是都没有，1是有4,2是有8，p表示是否贴着上限。
代码：

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

long long f[11][10][4][2][3][2];
char s1[12],s2[12];

long long dp(char *s)
{
    memset(f,0,sizeof(f));
    for(int i=1;i<=s[0]-'0';i++)
    f[0][i][1][0][(i%4==0)?i/4:0][i==s[0]-'0']=1;
    for(int i=0;i<10;i++)//第i位 
    for(int j=0;j<10;j++)//第i位的值 
    for(int k=1;k<4;k++)//连续k个 
    for(int l=(k==3);l<2;l++)//满不满足3个连续 
    for(int o=0;o<3;o++)//8和4的状态 
    for(int p=0;p<2;p++)//是否贴着上限 
    {
        int lim=p?s[i+1]-'0':9;/*
        if(f[i][j][k][l][o][p])
        printf("lim:%d i:%d j:%d k:%d l:%d o:%d p:%d f:%d\n",lim,i,j,k,l,o,p,f[i][j][k][l][o][p]);*/
        for(int u=0;u<=lim;u++)
        {
            int hh=(u==j)?min(k+1,3):1,oo=(o|((u%4==0)?u/4:0));//hh:连续 oo:8和4的状态 
            if(oo==3)
            continue;/*
            if(f[i][j][k][l][o][p])
            printf("%d %d %d %d %d %d\n",i+1,u,hh,l|(hh==3),oo,p&&u==lim);*/
            f[i+1][u][hh][l|(hh==3)][oo][p&&u==lim]+=f[i][j][k][l][o][p];
        }/*
        if(f[i][j][k][l][o][p])
        system("pause");*/
    }
    long long ans=0;
    for(int j=0;j<10;j++)
    for(int k=1;k<4;k++)
    for(int o=0;o<3;o++)
    for(int p=0;p<2;p++)
    ans+=f[10][j][k][1][o][p];
    return ans;
}
bool chk(char *s)
{
    bool eight=0,four=0;
    int con=0,mx=0;
    for(int i=0;i<11;i++)
    {
        if(i==0||s[i]!=s[i-1])
        {
            mx=max(mx,con);
            con=1;
        }
        else
        con++;
        if(s[i]=='4')
        four=1;
        else if(s[i]=='8')
        eight=1;
    }
    mx=max(mx,con);
    return (eight==0||four==0)&&mx>=3;
}
int main()
{
    scanf("%s%s",s1,s2);
    printf("%lld",dp(s2)-dp(s1)+chk(s1));
}