bzoj1026: [SCOI2009]windy数 数位dp
标签：out blank script 标记 包括 数位 ble nbsp put
题目：
http://www.lydsy.com/JudgeOnline/problem.php?id=1026
题意：
Description
windy定义了一种windy数。不含前导零且相邻两个数字之差至少为2的正整数被称为windy数。 windy想知道，
在A和B之间，包括A和B，总共有多少个windy数？
Input
包含两个整数，A B。
Output
一个整数
思路：
数位dp，记忆化搜索。
1 #include 2
3 using namespace std;
4
5 const int N = 30 + 10;
6
7 int dp[N][10];//定义dp[i][j]为第i位前驱数字为j时的方案数，注意前驱要合法
8 int dig[N];
9 int tot = 0;
10 int dfs(int pos, int pre, bool f, bool limit)
11 {//f用来标记是否有合法前驱
12 if(pos 1) return 1;
13 if(!limit && f && dp[pos][pre] != -1) return dp[pos][pre];
14 int en = limit ? dig[pos] : 9;
15 int ans = 0;
16 for(int i = 0; i )
17 if(! f) ans += dfs(pos-1, i, f || i != 0, limit && i == en);
18 else if(abs(i - pre) >= 2) ans += dfs(pos-1, i, f || i != 0, limit && i == en);
19 if(! limit && f) dp[pos][pre] = ans;
20 return ans;
21 }
22 int work(int n)
23 {
24 int tn = n;
25 tot = 0;
26 while(tn) dig[++tot] = tn % 10, tn /= 10;
27 memset(dp, -1, sizeof dp);
28 return dfs(tot, 0, 0, 1);
29 }
30 int main()
31 {
32 int n, m;
33 while(~ scanf("%d%d", &n, &m))
34 printf("%d\n", work(m) - work(n-1));
35 return 0;
36 }
bzoj1026: [SCOI2009]windy数 数位dp
标签：out blank script 标记 包括 数位 ble nbsp put
原文地址：http://www.cnblogs.com/jsszwc/p/7527261.html
评论