【Luogu】P2657windy数（数位DP）

2021-02-17 23:18

阅读：564

　　题目链接

　　正式迈入了数位DP的大门……

　　心情激动

　　（看我立个flag，我如果专攻数位DP的话，到wc之前就会有秒数位DP蓝题的能力）

　　数位DP讲解链接

　　讲的非常详细，良心博客。比我写的博客加在一起还要良心。

　　设f[i][j]表示第i位，上一位是j的方案数。

　　按照那篇博客的指示枚举即可，注意判断前导零。

#include
#include
#include
#include
#include
#includeusing namespace std;

inline long long read(){
    long long num=0,f=1;
    char ch=getchar();
    while(!isdigit(ch)){
        if(ch==‘-‘)    f=-1;
        ch=getchar();
    }
    while(isdigit(ch)){
        num=num*10+ch-‘0‘;
        ch=getchar();
    }
    return num*f;
}


int f[22][12]; //位数，上一位是什么
int d[30];

int dfs(int pos,bool limit,bool lead,int pre){
    if(pos==0)    return 1;
    if(limit==0&&lead==0&&f[pos][pre]!=-1)    return f[pos][pre];
    int up=limit==1?d[pos]:9;
    int ans=0;
    for(int i=0;ii){
        if(abs(i-pre)2&&lead==0)    continue;
        ans+=dfs(pos-1,limit&&i==d[pos],lead&&i==0,i);
    }
    if(limit==0&&lead==0)    f[pos][pre]=ans;
    return ans;
}

int calc(int num){
    int ret=num,len=0;
    while(ret){
        d[++len]=ret%10;
        ret/=10;
    }
    return dfs(len,1,1,0);
}

int main(){
    memset(f,-1,sizeof(f));
    int a=read(),b=read();
    printf("%d\n",calc(b)-calc(a-1));
    return 0;
}

上一篇：windows常见快捷键

下一篇：在iframe窗体内获取父级的元素；；在父窗口中获取iframe中的元素

文章来自：搜素材网的编程语言模块，转载请注明文章出处。
文章标题：【Luogu】P2657windy数（数位DP）
文章链接：http://soscw.com/index.php/essay/56789.html

亲，登录后才可以留言！

【Luogu】P2657windy数（数位DP）

评论

热门文章

推荐文章

最新文章

置顶文章