长乐一中 Day 6 2023/7/20

数位DP

用wbx的话来说是历史遗留性问题，俗称：我一直都不会

所以今天去重学了一下，感觉其实也没那么难，开始为自己为什么一直都不会感到奇怪。

T1

link

大概是模板题（

大概思路是先拆数然后记忆化dfs，当遇到特殊情况或者边界就return（数位dp都一个样

code:

#include
#define int long long
using namespace std;
int num[20],dp[20][2][2][10][2][2][2];
int dfs(int i,bool p4,bool p8,int pre,bool p3,bool bo,bool lim){
    if (p4&&p8){
        return 0;
    }
    if (!i){
        return p3;
    }
    if (~dp[i][p4][p8][pre][p3][bo][lim]){
        return dp[i][p4][p8][pre][p3][bo][lim];
    }
    int ret=0,li=9;
    if (lim){
        li=num[i];
    }
    for (int j=0;j<=li;j++){
        ret+=dfs(i-1,(j==4)||p4,(j==8)||p8,j,((j==pre)&&bo)||p3,j==pre,lim&&(j==li));
    }
    return dp[i][p4][p8][pre][p3][bo][lim]=ret;
}
int solve(int x){
    if (x<1e10){
        return 0;
    }
    memset(dp,-1,sizeof dp);
    int cnt=0,ret=0;
    while (x){
        num[++cnt]=x%10;
        x/=10;
    }
    for (int i=1;i<=num[11];i++){
        ret+=dfs(10,i==4,i==8,i,0,0,i==num[11]);
    } 
    return ret;
}
signed main()
{
    freopen("number.in","r",stdin);
    freopen("number.out","w",stdout);
    int l,r;
    scanf("%lld%lld",&l,&r);
    printf("%lld",solve(r)-solve(l-1));
    return 0;
}

T2和T3特别抽象，待会再看。

树形DP

都很抽象。让我再看看（