uestc 250 windy数【数位dp】

迈不过友情╰ 2022-08-13 13:37 160阅读 0赞

题目：[uestc 250 windy数][uestc 250 windy]

题意：

windy定义了一种windy数。

不含前导零且相邻两个数字之差至少为2的正整数被称为windy数。

分析：首先定义dp【i】【j】：有 i 位最高位为 j 的出现次数。

首先通过暴力预处理出dp值来。

很明显其满足区间减法，通过求0---x的值通过区间减法求x---y 的。

那么假如我们要求0---257的，

首先求0---99，直接遍历0---9的然后10--90的依次求出。

然后求100--200的，直接遍历100--200求和即可

最后求200--257的，我们依次求2和相邻的5之间差值超过2的，求和，然后5和相邻7之间差值超过2的，加油相邻小于2的，直接不满足跳出

AC代码：

#include <cstdio>
    #include <cstring>
    #include <vector>
    #include <algorithm>
    #include <map>
    #include <string>
    #include <iostream>
    #include <cmath>
    using namespace std;
    #define Del(a,b) memset(a,b,sizeof(a))
    typedef long long LL;
    const double esp = 1e-10;
    const long long N = 15;
    int dp[N][10];  //最高位
    void isit()
    {
        memset(dp,0,sizeof(dp));
        for(int i=0;i<=9;i++)
            dp[1][i]=1;
        for(int i=2;i<N;i++)
        {
            for(int j=0;j<=9;j++)
            {
                for(int k= 0;k<=9;k++)
                    if(abs(j-k)>=2)
                    dp[i][j]+=dp[i-1][k];
            }
        }
        //printf("%d\n",dp[3][1]);
    }
    int solve(int x){
        int digit[20],cnt=0;
        while(x){
            digit[++cnt]=x%10;
            x/=10;
        }
        int ans=0;
        for(int i=1;i<cnt;i++)  //先把长度为1至cnt-1计入
            for(int j=1;j<10;j++)
                ans+=dp[i][j];
        for(int j=1;j<digit[cnt];j++)   //确定最高位
            ans+=dp[cnt][j];
        for(int i=cnt-1;i>0;i--){
            for(int j=0;j<digit[i];j++)
                if(abs(j-digit[i+1])>=2)
                    ans+=dp[i][j];
            if(abs(digit[i]-digit[i+1])<2)  //如果高位已经出现非法，直接退出
                break;
        }
        return ans;
    }
    int main()
    {
        isit();
        int x,y;
        while(~scanf("%d%d",&x,&y))
        {
            printf("%d\n",solve(y+1)-solve(x));
        }
        return 0;
    }

[uestc 250 windy]: http://www.acm.uestc.edu.cn/#/problem/show/250