首页 > 代码库 > uestc 250 windy数 【数位dp】

uestc 250 windy数 【数位dp】

题目: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数 【数位dp】