首页 > 代码库 > windy数(简单数位DP)

windy数(简单数位DP)

2024-08-18 18:29:50   219人阅读

1026: [SCOI2009]windy数

Time Limit: 1 Sec  Memory Limit: 162 MB
Submit: 6306  Solved: 2810
[Submit][Status][Discuss]

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，看了题解，觉得好有意思啊，觉得好神奇啊，希望以后可以多做几个

思路是：首先，DP[i][j]的意思是 j 是首位的 i 位的数的这段区间里有多少windy数，例如 dp[2][5] 就是 50-59 内有多少 windy 数

有了这个 dp 数组后，就要开始解决问题了， 将一个数慢慢逼近，所以，最后的值会是 1 --  n-1 中的 windy 数

 

技术分享
 1 #include<stdio.h> 2 #include<math.h> 3 #include<stdlib.h> 4 #include<string.h> 5  6 int dp[15][15]; 7  8 void Init() 9 {10     memset(dp,0,sizeof(dp));11     int i,j,k;12     for (i=0;i<10;i++)13     dp[1][i]=1;14     15     for (i=2;i<=10;i++)16     {17         for (j=0;j<10;j++)18         {19             for (k=0;k<10;k++)20             if (abs(j-k)>=2)21             dp[i][j]+=dp[i-1][k];22         }23     }24 }25 26 27 int slove(int x)28 {29     int len=0;30     int w[15];31     while (x)32     {33         w[++len]=x%10;34         x/=10;35     }36     w[len+1]=0;37     int ans=0;38     int i,j;39     for (i=1;i<len;i++)40     for (j=1;j<10;j++)41     ans+=dp[i][j];42     43     for (i=1;i<w[len];i++)44     ans+=dp[len][i];45     46     for (i=len-1;i;i--)47     {48         for (j=0;j<w[i];j++)49         {50             if (abs(w[i+1]-j)>=2)51             ans+=dp[i][j];52         }53         if (abs(w[i+1]-w[i])<2)54         break;55     }56     return ans;57 }58 59 int main()60 {61     Init();62     int l,r;63     while (scanf("%d%d",&l,&r)!=EOF)64     {65         printf("%d\n",slove(r+1)-slove(l));66     }67     return 0;68 }
View Code

 

 

 

windy数(简单数位DP)


联系
我们