1026: [SCOI2009]windy数（数位dp)

本文主要是介绍1026: [SCOI2009]windy数（数位dp)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

1026: [SCOI2009]windy数
Time Limit: 1 Sec Memory Limit: 162 MB
Submit: 12141 Solved: 5770
[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
【输出样例一】

【输出样例二】

20
HINT
【数据规模和约定】

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

Source

思路： 比起不要62来说，多了前导0的考虑，也就是last这一维状态，表示上一个数字，为0的话表示-10.

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>using namespace std;int dp[105][10];
int cnt,num[105];int dfs(int len,int last,bool limit)
{if(len == 0){return 1;}if(!limit && dp[len][last] && last >= 0)return dp[len][last];int ans = 0;int up = (limit ? num[len] : 9);for(int i = 0;i <= up;i++){if(abs(i - last) < 2)continue;int now = i;if(i == 0 && last == -10)now = -10;ans += dfs(len - 1,now,limit && (i == up));}if(!limit && last >= 0)//只有没有限制的时候才能记忆化return dp[len][last] = ans;elsereturn ans;
}int solve(int n)
{memset(dp,0,sizeof(dp));cnt = 0;while(n){num[++cnt] = n % 10;n /= 10;}return dfs(cnt,-10,true);
}int main()
{int m,n;scanf("%d%d",&m,&n);printf("%d\n",solve(n) - solve(m - 1));return 0;
}

递推写法

#include <cstdio>
#include <cstring>
#include <algorithm>using namespace std;int digit[20];
int f[20][20];void DP()
{for(int i = 0;i <= 9;i++){f[1][i] = 1;}for(int i = 2;i <= 10;i++){for(int j = 0;j <= 9;j++){for(int k = 0;k <= 9;k++){if(abs(j - k) >= 2)f[i][j] += f[i - 1][k];}}}
}int solve(int x)
{int len = 0;while(x){digit[++len] = x % 10;x /= 10;}int ans = 0;for(int i = 1;i < len;i++){for(int j = 1;j <= 9;j++){ans += f[i][j];}}for(int i = 1;i < digit[len];i++){ans += f[len][i];}int i;for(i = len - 1;i >= 1;i--){for(int j = 0;j < digit[i];j++){if(abs(digit[i + 1] - j) >= 2){ans += f[i][j];}}if(abs(digit[i + 1] - digit[i]) < 2)break;}if(i == 0)ans++;return ans;
}int main()
{DP();int a,b;scanf("%d%d",&a,&b);printf("%d\n",solve(b) - solve(a - 1));return 0;
}