数位dp BZOJ 1026: [SCOI2009]windy数

1026: [SCOI2009]windy数

Time Limit: 1 Sec Memory Limit: 162 MB
Submit: 2242 Solved: 976
[ Submit][ Status]

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

【数据规模和约定】
20%的数据，满足 1 <= A <= B <= 1000000 。
100%的数据，满足 1 <= A <= B <= 2000000000 。

思路：很裸的数位dp。。。。

代码：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <string.h>
#include <algorithm>
using namespace std;
#define LL long long
LL dp[20][10];
char bit[20]; int n;

inline int abs(int x) { return x<0?-x:x; }

void pre_init()
{
    memset(dp,0,sizeof(dp));
    for(int i=0;i<=9;++i) dp[1][i]=1;
    for(int i=1;i<19;++i) {
        for(int v1=0;v1<=9;++v1)
        for(int v2=0;v2<=9;++v2) if(abs(v2-v1)>=2)
            dp[i+1][v2]+=dp[i][v1];
    }
}

LL dfs(int cur,int pre,bool limit,bool all_zero,int first)
{
    if(cur==0) return 1;
    LL ret=0;
    if(!limit) {
        for(int v=0;v<=9;++v)
        if(abs(pre-v)>=2 || all_zero) ret+=dp[cur][v];
        return ret;
    }
    int tail=limit?bit[cur]-'0':9;
    for(int v=first;v<=tail;++v)
    if(abs(pre-v)>=2 || all_zero)
        ret+=dfs(cur-1,v,limit&&v==tail,all_zero&&v==0,0);
    return ret;
}

void tobit(LL x)
{
    n=0;
    if(x==0) bit[++n]='0';
    while(x>0) {
        bit[++n]=x%10+'0';
        x/=10;
    }
    bit[n+1]='\0';
}

void GetData()
{
    freopen("in.txt","w",stdout);
    for(int i=0;i<100;++i) {
        int x=rand();
        printf("%d %d\n",x,x+rand());
    }
}

bool ok(LL x)
{
    int v=x%10; x/=10;
    while(x>0) {
        int diff=abs((x%10)-v);
        if(diff<2) return false;
        v=x%10;
        x/=10;
    }
    return true;
}

int main()
{
 //   GetData(); return 0;
    //freopen("in.txt","r",stdin);
    //9961 10034
    LL a,b;
    pre_init();
    while(cin>>a>>b) {
        --a; tobit(a);// printf("%s ",bit+1);
        LL ans=dfs(n,-100,true,true,1);
        for(int i=1;i<n;++i) for(int j=1;j<=9;++j)
            ans+=dp[i][j];
        tobit(b); //printf("%s\n",bit+1);
        ans = -ans;
        ans += dfs(n,-100,true,true,1);//-ans;
        for(int i=1;i<n;++i) for(int j=1;j<=9;++j)
            ans+=dp[i][j];
        cout<<ans<<endl;
    }
}