BZOJ4521 Cqoi2016 手机号码【数位DP】

Description

人们选择手机号码时都希望号码好记、吉利。比如号码中含有几位相邻的相同数字、不含谐音不吉利的数字等。手机运营商在发行新号码时也会考虑这些因素，从号段中选取含有某些特征的号码单独出售。为了便于前期规划，运营商希望开发一个工具来自动统计号段中满足特征的号码数量。
工具需要检测的号码特征有两个：号码中要出现至少3个相邻的相同数字，号码中不能同时出现8和4。号码必须同时包含两个特征才满足条件。满足条件的号码例如：13000988721、23333333333、14444101000。而不满足条件的号码例如：1015400080、10010012022。
手机号码一定是11位数，前不含前导的0。工具接收两个数L和R，自动统计出[L,R]区间内所有满足条件的号码数量。L和R也是11位的手机号码。

Input

输入文件内容只有一行，为空格分隔的2个正整数L,R。
10^10 < = L < = R < 10^11

Output

输出文件内容只有一行，为1个整数，表示满足条件的手机号数量。

Sample Input

12121284000 12121285550

Sample Output

样例解释

满足条件的号码： 12121285000、 12121285111、 12121285222、 12121285333、 12121285550

数位DP，维数太多不想多说了

维护当前第几位，上一位填的数，上上位填的数，是否出现过三连，是否出现过4，是否出现过8，是否到达上限

然后乱搞
注意特判一下首位不能为0就好了

#include<bits/stdc++.h>

using namespace std;

#define LL long long

LL dp[12][11][11][2][2][2][2];

LL p[20];

LL dfs(LL len,LL las,LL llas,LL thri,LL has4,LL has8,LL up){

    if(len==10&&las==0)return 0;

    if(!len)return thri;

    if(dp[len][las][llas][thri][has4][has8][up])

        return dp[len][las][llas][thri][has4][has8][up];

    LL r=up?p[len]:9,res=0;

    for(LL i=0;i<=r;i++)

        if(!(i==4&&has8)&&!(i==8&&has4))

            res+=dfs(len-1,i,las,thri||(i==las&&i==llas),has4||i==4,has8||i==8,up&&i==r);

    return dp[len][las][llas][thri][has4][has8][up]=res;

}

LL solve(LL t){

    memset(dp,0,sizeof(dp));

    LL len=0;

    while(t){

        p[++len]=t%10;

        t/=10;

    }

    return dfs(len,0,0,0,0,0,1);

}

int main(){

    LL a,b;cin>>a>>b;

    cout<<solve(b)-solve(a-1);

    return 0;

}

巴特西

BZOJ4521 Cqoi2016 手机号码【数位DP】

Description

Input

Output

Sample Input

Sample Output

样例解释

最新文章

热门文章

巴特西

BZOJ4521 Cqoi2016 手机号码 【数位DP】

Description

Input

Output

Sample Input

Sample Output

样例解释

最新文章

热门文章

BZOJ4521 Cqoi2016 手机号码【数位DP】