P2657 [SCOI2009]windy数

2021-03-20 20:26

阅读：485

标签：mat math cst namespace names print win abs ring

注意此类要处理前导零的数位DP题，因为如果前面全是0，这一位可以填0和1。

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

int dp[20][20],num[20];

inline int dfs(int now,int pre,bool limit)
{
    if(now==0) return 1;
    if(dp[now][pre]!=-1&&!limit) return dp[now][pre];
    int ans=0,up=9;
    if(limit) up=num[now];
    for(register int i=0;ii)
    {
        if((abs(i-pre))2) continue;
        if(i==0&&pre==-10) ans+=dfs(now-1,-10,limit&&(i==num[now]));
        else ans+=dfs(now-1,i,limit&&(i==num[now]));
    }
    if(!limit) dp[now][pre]=ans;
    return ans;
}

inline int solve(int k)
{
    memset(dp,-1,sizeof(dp));
    int pos=0;
    while(k>0)
    {
        num[++pos]=k%10;
        k/=10;
    }
    return dfs(pos,-10,true);
}

int main()
{
    int x,y;
    scanf("%d%d",&x,&y);
    printf("%d\n",solve(y)-solve(x-1));
    return 0;
}

P2657 [SCOI2009]windy数

标签：mat math cst namespace names print win abs ring

原文地址：https://www.cnblogs.com/Hoyoak/p/11840144.html

上一篇：C#中将xml文件反序列化为实例时采用基类还是派生类的问题

下一篇：windows下RocketMQ安装部署

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

亲，登录后才可以留言！

P2657 [SCOI2009]windy数

评论

热门文章

推荐文章

最新文章

置顶文章