动态规划-数位DPwindy

https://vjudge.net/contest/297216?tdsourcetag=s_pctim_aiomsg#problem/L

#include<bits/stdc++.h>

//#include<math.h>

//#include<stdio.h>

using namespace std;

#define LL long long

const int maxn=2e9+;

LL f[][]; // 设f[i,j]表示由前i位数字构成且最高位数字为j的windy数有多少个

LL a[];

void init() // 预处理f[i,j]数组

{

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

        f[][i]=;

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

    {

        for(int j=; j<=; j++)

        {

            int l=j-,r=j+;

            for(int k=l; k>=; k--)

                f[i][j]+=f[i-][k];

            for(int k=r; k<=; k++)

                f[i][j]+=f[i-][k];

        }

    }

}

int fun(LL t) // 这个来求[1-t]区间之间有多少winfy数

{

    if(t<) return t;

    int len=;

    while(t)

    {

        a[++len]=t%;

        t/=;

    }

    LL sum=; // 首先，求位数小于这个数的所有windy数

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

        for(int j=; j<=; j++)

            sum+=f[i][j];

             // 求位数等于这个数，最高位小于这个数的最高位的windy数

    for(int i=; i<a[len]; i++)

        sum+=f[len][i];

    for(int i=len-; i>=; i--)

    {

        for(int j=; j<=; j++)

        {

            if(abs(j-a[i+])>=&&j<a[i])

                sum+=f[i][j];

        }

        if(abs(a[i+]-a[i])<)

            break;

        if(i==)++sum; // 这里注意如果最后一位也满足与上一位差值>=2，需要+1

    }

    return sum;

}

int main()

{

    init();

    LL a,b;

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

    LL sum1=fun(b);

    LL sum2=fun(a-);// 这里注意因为要取到a，所有求a-1之前的数

    printf("%lld",sum1-sum2);

}