长乐 DAY11

今天是数位DP和树状DP，结果树状DP里两题博弈论……贴段数位DP代码

#include
using namespace std;
long long l,r,dp[15][13][13][2][2][2];
int u[99];
long long dfs(int res,int a,int b,bool st,bool e,bool f,bool lt)
{
    if(e && f) return 0;
    if(!res) return st;
    if(!lt && dp[res][a][b][st][e][f]!=-1) return dp[res][a][b][st][e][f];
    long long sum=0;
    int maxn=lt?u[res]:9;
    for(int i=0;i<=maxn;i++)
        sum+=dfs(res-1,i,a,st || (i==a && i==b),e || (i==8),f || (i==4),lt && i==maxn);
    if(!lt) dp[res][a][b][st][e][f]=sum;
    return sum;
}
long long find(long long x)
{
    int tot=0;
    while(x)
    {
        u[++tot]=x%10;
        x/=10;
    }
    if(tot<11) return 0;
    memset(dp,-1,sizeof(dp));
    long long ans=0;
    for(int i=1;i<=u[tot];i++)
        ans+=dfs(tot-1,i,0,0,i==8,i==4,i==u[tot]);
    return ans;
}
int main()
{
    freopen("number.in","r",stdin);
    freopen("number.out","w",stdout);
    scanf("%lld%lld",&l,&r);
    printf("%lld",find(r)-find(l-1));
    return 0;
}