BZOJ 1026 windy数【数位DP】

1026: [SCOI2009]windy数

Time Limit: 1 Sec Memory Limit: 162 MB
Submit: 10142 Solved: 4712
[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 。

#include<cstdio>

#include<string>

#include<cstdlib>

#include<cmath>

#include<iostream>

#include<cstring>

#include<set>

#include<queue>

#include<algorithm>

#include<vector>

#include<map>

#include<cctype>

#include<stack>

#include<sstream>

#include<list>

#include<assert.h>

#include<bitset>

#include<numeric>

#define debug() puts("++++")

#define gcd(a,b) __gcd(a,b)

#define lson l,m,rt<<1

#define rson m+1,r,rt<<1|1

#define fi first

#define se second

#define pb push_back

#define sqr(x) ((x)*(x))

#define ms(a,b) memset(a,b,sizeof(a))

#define sz size()

#define be begin()

#define pu push_up

#define pd push_down

#define cl clear()

#define lowbit(x) -x&x

#define all 1,n,1

#define rep(i,x,n) for(int i=(x); i<=(n); i++)

using namespace std;

typedef long long LL;

typedef unsigned long long ULL;

typedef pair<int,int> P;

const int INF = 0x3f3f3f3f;

const LL LNF = 1e18;

const int maxm = 1e6 + ;

const double PI = acos(-1.0);

const double eps = 1e-;

const int dx[] = {-,,,,,,-,-};

const int dy[] = {,,,-,,-,,-};

int dir[][] = {{,},{,-},{-,},{,}};

const int mon[] = {, , , , , , , , , , , , };

const int monn[] = {, , , , , , , , , , , , };

const int mod = ;

#define inf 0x3f3f3f3f

#define ll long long

const int maxn = ;

int digit[];

//49 //62 \ 4

ll dp[][]; //第一个参数：数位 第二个参数：

//对每个数位上的状态进行dfs，模拟正常数数的过程

//if6——》(状态)当前数是否是4,他的上一位是否是4

ll dfs(int len, int last ,bool limit)//limit代表他的上一位是否是上界

{

    int p;

    if(len<=) return ;//个位

    if(!limit && dp[len][last]!=- && last>= ) return dp[len][last];//5123 还没有到5——0 1 2 3 4 //记忆化搜索

    ll cnt=,up_bound=(limit?digit[len]:);

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

    {

        if(abs(i-last)<) continue; //剪62枝

        p=i;

        if(i== && last==-) p=last;

        cnt += dfs(len-, p, limit && i==up_bound);

    }

    if(!limit && last>=) dp[len][last]=cnt; //完整状态

    return cnt;

}

ll solve(ll num)

{

    int k=; //记录有多少个数位

    while(num)

    {

        digit[++k]=num%;

        num/=;

    }

    ms(dp,);

    return dfs(k,-,true);

}

int main()

{

    int t;

    ll n,m;

    while(~scanf("%lld%lld",&n,&m))

    {

        printf("%lld\n",solve(m)-solve(n-));

    }

}

/*

【输入样例一】

1 10

9

25 50

20

*/

秒客网