bzoj千题计划117：bzoj1026: [SCOI2009]windy数

http://www.lydsy.com/JudgeOnline/problem.php?id=1026

数位DP

如果前一位填的是0，

0是前导0，下一位可以随便填

0不是前导0，下一位不能填1

为避免这种情况

枚举位数，强制不出现前导0

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

int dp[][];

int a[];

int LEN;

int dfs(int dep,int num,bool lim)

{

    if(!lim && dp[dep][num]!=-) return dp[dep][num];

    if(!dep) return ;

    int up= lim ? a[dep] : ,tmp=;

    for(int i=;i<=up;++i)

    {

        if(dep==LEN && !i) continue;

        if(abs(i-num)<) continue;

        tmp+=dfs(dep-,i,lim && i==up);

    }

    if(!lim) dp[dep][num]=tmp;

    return tmp;

}

int solve(int n)

{

    if(!n) return ;

    int len=;

    while(n)

    {

        a[++len]=n%;

        n/=;

    }

    int sum=;

    for(int i=;i<len;++i)

    {

        LEN=i;

        sum+=dfs(i,,);

    }

    LEN=len;

    sum+=dfs(len,,);

    return sum;

}

int main()

{

    int a,b;

    scanf("%d%d",&a,&b);

    memset(dp,-,sizeof(dp));

    printf("%d\n",solve(b)-solve(a-));

}

或者是记录有无前导零这个状态

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

int dp[][][];

int a[];

int LEN;

int dfs(int dep,int num,bool lim,bool zero)

{

    if(!lim && dp[dep][num][zero]!=-) return dp[dep][num][zero];

    if(!dep) return !zero;

    int up= lim ? a[dep] : ,tmp=;

    for(int i=;i<=up;++i)

    {

        if(abs(i-num)< && !zero) continue;

        tmp+=dfs(dep-,i,lim && i==up,zero && !i);

    }

    if(!lim) dp[dep][num][zero]=tmp;

    return tmp;

}

int solve(int n)

{

    if(!n) return ;

    int len=;

    while(n)

    {

        a[++len]=n%;

        n/=;

    }

    return dfs(len,,,);

}

int main()

{

    int a,b;

    scanf("%d%d",&a,&b);

    memset(dp,-,sizeof(dp));

    printf("%d\n",solve(b)-solve(a-));

}

1026: [SCOI2009]windy数

Time Limit: 1 Sec Memory Limit: 162 MB
Submit: 8771 Solved: 3959
[Submit][Status][Discuss]

Description

　　windy定义了一种windy数。不含前导零且相邻两个数字之差至少为2的正整数被称为windy数。 windy想知道，
在A和B之间，包括A和B，总共有多少个windy数？

Input

　　包含两个整数，A B。

Output

　　一个整数

Sample Input

【输入样例一】
1 10
【输入样例二】
25 50

Sample Output

【输出样例一】
9
【输出样例二】
20

HINT

【数据规模和约定】

100%的数据，满足 1 <= A <= B <= 2000000000 。

巴特西