HYSBZ 1026 windy数数位dp

2022-09-07 08:32:55

点击打开链接

windy数

Time Limit: 1 Sec Memory Limit: 162 MB
Submit: 3038 Solved: 1361
[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

HINT

【数据规模和约定】

100%的数据，满足 1 <= A <= B <= 2000000000 。

感觉和上一题差不多。。。

状态转移方程也好推：

dp[i][j]+=dp[i-1][k] （fabs(j-k)>=2)

dp[i][j]表示第i位上数字为j的满足情况的个数。

//804 KB	0 ms
#include<stdio.h>
#include<string.h>
#include<math.h>
using namespace std;
int dp[12][10],a[12];
void init()
{
    memset(dp,0,sizeof(dp));
    for(int i=0;i<=9;i++)dp[1][i]=1;
    for(int i=2;i<=11;i++)
        for(int j=0;j<=9;j++)
            for(int k=0;k<=9;k++)
                if(k-j>=2||j-k>=2)dp[i][j]+=dp[i-1][k];
}
int solve(int num)
{
    int k=0,sum=0;
    while(num)//将数字分解存到数组a里面
    {
        a[++k]=num%10;
        num/=10;
    }
    a[k+1]=0;
    for(int i=1;i<k;i++)//从个位一直加到最高位-1
        for(int j=1;j<=9;j++)
            sum+=dp[i][j];
    for(int i=1;i<a[k];i++)
        sum+=dp[k][i];
    for(int i=k-1;i>=1;i--)
    {
        for(int j=a[i]-1;j>=0;j--)//如果上位和这位的差大于等于2，就加上这位从0到a[i]-1的所有情况
            if(fabs(a[i+1]-j)>=2)sum+=dp[i][j];
        if(fabs(a[i+1]-a[i])<2)break;//如果上一位和这位的差小于2，就结束
    }
    return sum;
}
int main()
{
    init();
    int l,r;
    while(scanf("%d%d",&l,&r)!=EOF)
        printf("%d\n",solve(r+1)-solve(l));
}