P4124——手机号码

为什么我感觉数位dp都长得一样呢,好像直接记搜都能过???

第一个脑回路清晰的数位dp。记一下上一个,上上个,有没有限制,有没有4,有没有8,然后直接dfs爆搜就完了。

不过这有坑,就是一开始初始化的时候第len-1的上上个,不能赋成一个贼大的值,比9大即可。还有一个就是要判边界,当l==10000000000时,直接输出slove(r);

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<vector>
#include<cmath>
#include<queue>
#include<map>
#include<set>
#define ri register int
#define max maxx
#define min minn
using namespace std;
template <class T> void in(T &x)
{
    x = 0;
    bool f = 0;
    char c = getchar();
    while (c < '0' || c > '9')
    {
        if (c == '-') f = 1;
        c = getchar();
    }
    while ('0' <= c && c <= '9')
    {
        x = (x << 3) + (x << 1) + (c ^ 48);
        c = getchar();
    }
    if (f) x = -x;
}
inline int maxx(int x,int y)
{
    return x>y?x:y;
}
inline int minn(int x,int y)
{
    return x<y?x:y;
}
inline int gcd(int x,int y)
{
    return !y?x:gcd(y,x%y);
}
long long dp[20][11][11][4][4][4],l,r,len,ans,flag,num[20];
inline long long dfs(int temp,int last,int lasts,int limit,int ans,int four,int eight)
{
    if(temp<=0)
        return ans;
    if((!limit)&&dp[temp][last][lasts][ans][four][eight])
        return dp[temp][last][lasts][ans][four][eight];
    long long lim=limit?num[temp]:9,tmp=0;
    for(ri i=0; i<=lim; ++i)
    {
        if((i==last)&&(last==lasts))
            flag=1;
        else
            flag=0;
        if(i==4&&eight)
            continue;
        if(i==8&&four)
            continue;
        tmp+=dfs(temp-1,i,last,limit&&i==lim,ans||flag,four||i==4,eight||i==8);
    }
    return !limit?dp[temp][last][lasts][ans][four][eight]=tmp:tmp;
}
inline long long solve(long long x)
{
    ans=0;
    len=0;
    memset(dp,0,sizeof dp);
    while(x)
        num[++len]=(x%10),x/=10;
    for(ri i=1; i<=num[len]; ++i)
        ans+=dfs(len-1,i,233,(i==num[len]),0,i==4,i==8);
    return ans;
}
int main()
{
    scanf("%lld%lld",&l,&r);
    l==10000000000?printf("%lld",solve(r)):printf("%lld",solve(r)-solve(l-1));
    return 0;
}

发表于 2018-08-28 09:36:29 in 题目