洛谷 P2657 [SCOI2009]windy数解题报告

P2657 [SCOI2009]windy数

题目描述

( t{windy})定义了一种( t{windy})数。不含前导零且相邻两个数字之差至少为(2)的正整数被称为( t{windy})数。 ( t{windy})想知道，

在(A)和(B)之间，包括(A)和(B)，总共有多少个( t{windy})数？

输入输出格式

输入格式：

包含两个整数，(A) (B)。

输出格式：

一个整数

说明

(100\%)的数据，满足 (1 le A le B le 2000000000) 。

跟着咕咕日报了解了一下套路的数位( t{DP})的写法，发现之前自己( t{yy})的太( t{naive})啦

思路是把前导(0)和高位限制放到记搜里面做参数直接解决。

Code:

#include <cstdio>
#include <cstring>
#include <algorithm>
int dp[12][10],a[12];
int dfs(int dep,int pre,int lead,int limit)//第几位,上一位的数字,前导0,高位是否有限制
{
    if(~dp[dep][pre]&&!lead&&(!limit||!dep)) return dp[dep][pre];
    if(dep==0) return 0;
    int res=limit?a[dep]:9,ret=0;
    for(int i=0;i<=res;i++)
    {
        if(!lead&&abs(pre-i)<2) continue;
        if(!i&&lead) ret+=dfs(dep-1,i,lead,limit&i==res);
        //选0且有前导0，仍然有
        if(i&&lead) ret+=dfs(dep-1,i,!lead,limit&i==res);
        //选0且无前导0，没了
        if(!lead) ret+=dfs(dep-1,i,lead,limit&i==res);
        //无前导0
    }
    if(!limit&&!lead) dp[dep][pre]=ret;
    return ret;
}
int solve(int n)
{
    if(!n) return 0;
    int cnt=0;
    for(int i=1;n;i++) a[++cnt]=n%10,n/=10;
    return dfs(cnt,0,1,1);
}
int main()
{
    int a,b;
    memset(dp,-1,sizeof(dp));
    for(int i=0;i<=9;i++) dp[0][i]=1;
    scanf("%d%d",&a,&b);
    printf("%d
",solve(b)-solve(a-1));
    return 0;
}

2018.11.6