Luogu P2602 [ZJOI2010]数字计数 //数位DP

（话说我打题真的好少状压好像也就才做了3道就滚来学数位了= =）

看题一眼数位DP（这个真的只能看看不出来也说不了什么）

数位DP老师教我们的是记忆化DFS写法好写不爆栈脑子不迷糊

特别注意处理前导0 ，数位DP好像难就难在处理前导零上吧 = =

爆搜的话想一想要往状态里塞什么东西

当我们搜完一个数，我们要知道什么时候搜完，搜完之后这个数能对答案产生多少贡献，以及这个数是否合法，如何向后推导

老师已经帮我把这些讲好了......

long long dfs(int pos , int pre ,int goal, bool limit , bool lead)

pos 表示现在搜到了第几位， pre表示前面有几个要数的数（原题要求1-9）

goal 表示现在在数的数， limit表示受限（这个后面说怎么用和怎么维护）， lead表示前导零状态

1 pos 搜到第几位不用说， pos从原数长开始，到0结束

　　（边界）

2 pre 表示到这一位之前有几个目标数字（比如23333里面在处理第4位时，前面有2个3）

　　用于计算答案

3 goal 目标数字原封不动往后传

　　用于辅助计算答案

4 limit 受限在搜的过程中要注意不能超过原数字大小，那么limit肯定是一个连续的状态，而且当这一位等于原数当前位的大小时，这个状态接着传递。

　　用来判断下一位最高可以取到哪

5 lead 前导零如果这一位之前的数都是前导0 那么之前的0 都是不数的

　　用于计算0时排除前导0的干扰

源代码在下面结合理解食用

#include<bits/stdc++.h>

using namespace std ;

long long dp[30][20],cap[30],cnt,n,m;

long long dfs(int pos , int pre ,int goal, bool limit , bool lead){
    if(pos == 0) {
        return pre ;
    }
    if(!limit && !lead && dp[pos][pre] != -1) return dp[pos][pre];
    int upp = (limit) ? cap[pos] : 9 ;
    long long ret = 0;
    for(int i=0; i <= upp; i++){
        ret += dfs(pos-1, ((i==goal) && (!lead || i)) ? pre + 1 : pre, goal, (i==cap[pos] && limit), (i==0 && lead));
    }
    if(!limit && !lead) dp[pos][pre] = ret;
    return ret;
}

long long solve (int dig,long long x){//注意这里的long long
    memset(cap,0,sizeof cap);
    memset(dp,0xff,sizeof dp);
    cnt=0;
    while (x){
        cnt++;
        cap[cnt]=x%10;
        x/=10;
    }
    return dfs(cnt , 0 , dig ,true ,true);
}

int main(){
    cin>>n>>m;
    for(int i=0;i<=9;i++){
        cout<<solve(i,m)-solve(i,n-1)<<" ";
    }
    puts ("");
    return 0;
}

TAG: SIN_XIII

Luogu P2602 [ZJOI2010]数字计数 //数位DP

相关推荐