windy数
Time Limit: 3000/1000MS (Java/Others) Memory Limit: 65535/65535KB (Java/Others)
Submit Status
windy定义了一种windy数。
不含前导零且相邻两个数字之差至少为2的正整数被称为windy数。
windy想知道，在A和B之间，包括A和B，总共有多少个windy数？
Input
包含两个整数，AA BB。
满足 1≤A≤B≤20000000001≤A≤B≤2000000000 .
Output
Sample input and output
| Sample Input | Sample Output |
|---|---|
1 10 | 9 |
Source
Windy
简单数位dp，注意前导0的情况即可。
# include# include # include int a[11], dp[11][10];int dfs(int pos, int pre, bool sta, int limit){ if(pos == -1) return 1; if(!limit && !sta&& dp[pos][pre] != -1) return dp[pos][pre]; int up = limit?a[pos]:9; int ans = 0; for(int i=0; i<=up; ++i) { if(sta) ans += dfs(pos-1, i, i==0, limit&&i==a[pos]); else if(abs(pre-i)>=2) ans += dfs(pos-1, i, false, limit&&i==a[pos]); } if(!limit && !sta) dp[pos][pre] = ans; return ans;}int solve(int num){ int pos = 0; while(num) { a[pos++] = num%10; num /= 10; } return dfs(pos-1, 0, true, true);}int main(){ memset(dp, -1, sizeof(dp)); int n, m; while(~scanf("%d%d",&n,&m)) printf("%d\n",solve(m)-solve(n-1)); return 0;}