[SCOI2009]windy数
标签：for std iostream ems pos dfs 一个 记忆 ==
1026: [SCOI2009]windy数
Time Limit: 1 Sec Memory Limit: 162 MB
Description
windy定义了一种windy数。不含前导零且相邻两个数字之差至少为2的正整数被称为windy数。 windy想知道，
在A和B之间，包括A和B，总共有多少个windy数？
Input
Output
Sample Input
【输入样例一】
1 10
【输入样例二】
25 50
Sample Output
【输出样例一】
9
【输出样例二】
20
HINT
第一次打数位dp，lc大佬讲完以后又问了问邢夫人差不多弄明白了，还是比较记忆化搜索的打法，很好理解，固定格式，不过对于前导0和上界需要处理一下。
1 #include 2 #include 3 #include 4 #include
5 #include 6 using namespace std;
7 int l,r,f[15][15],bit[15];
8 int dfs(int pos,int pre,bool Limit) {
9 if(pos0) return 1;
10 if(!Limit&&f[pos][pre]!=-1&&pre>=0) return f[pos][pre];
11 int End=Limit?bit[pos]:9,ans=0;
12 for(int i=0; ii) {
13 if(abs(i-pre)>=2) {
14 if(pre==-10&&!i) ans+=dfs(pos-1,pre,(Limit&&i==End));
15 else ans+=dfs(pos-1,i,(Limit&&i==End));
16 }
17 } if(!Limit&&pre>=0) f[pos][pre]=ans;
18 return ans;
19 }
20 int Calc(int x) {
21 memset(f,0xff,sizeof(f));
22 memset(bit,0,sizeof(bit));
23 while(x) bit[++bit[0]]=x%10,x/=10;
24 return dfs(bit[0],-10,true)+2;
25 }
26 int main() {
27 scanf("%d%d",&l,&r);
28 memset(f,0xff,sizeof(f));
29 printf("%d\n",Calc(r)-Calc(l-1));
30 return 0;
31 }
[SCOI2009]windy数
标签：for std iostream ems pos dfs 一个 记忆 ==
原文地址：http://www.cnblogs.com/forevergoodboy/p/7763869.html
评论