bzoj 1026 [SCOI2009]windy数——数位dp水题

2021-03-25 23:24

阅读：931

标签：|| can include color 数位 tps line div using

题目：https://www.lydsy.com/JudgeOnline/problem.php?id=1026

迷恋上用dfs写数位dp了。

#include
#include
#include
#include
using namespace std;
const int N=15;
int l,r,dg[N],dp[N][N];
int dfs(int p,int lst,bool fr,bool fx)
{
    if(!p)return 1;
    if(!fx&&dp[p][lst]!=-1)return dp[p][lst];
    int st=(fr?1:0),end=(fx?dg[p]:9);
    int ret=0;
    for(int i=st;i)
        if(fr||(abs(i-lst)>=2))
            ret+=dfs(p-1,i,0,fx&(i==dg[p]));
    if(!fx)dp[p][lst]=ret;
    return ret;
}
int calc(int x)
{
    int cnt=0,ret=0;
    while(x)dg[++cnt]=x%10,x/=10;
    for(int i=1;i)
    {
        memset(dp,-1,sizeof dp);//写在这里 
        ret+=dfs(i,0,1,(i==cnt));
    }
    return ret;
}
int main()
{
    scanf("%d%d",&l,&r);
    printf("%d\n",calc(r)-calc(l-1));
    return 0;
}

bzoj 1026 [SCOI2009]windy数——数位dp水题

标签：|| can include color 数位 tps line div using

原文地址：https://www.cnblogs.com/Narh/p/9402428.html

上一篇：居中的css:完全指南(翻译)

下一篇：C#数据结构—查找

文章来自：搜素材网的编程语言模块，转载请注明文章出处。
文章标题：bzoj 1026 [SCOI2009]windy数——数位dp水题
文章链接：http://soscw.com/index.php/essay/67981.html

亲，登录后才可以留言！

bzoj 1026 [SCOI2009]windy数——数位dp水题

评论

热门文章

推荐文章

最新文章

置顶文章