拓扑排序＆关键路径＆数位dp

      今上午看了拓扑排序和关键路径，了解了基本原理，至于代码还只看了模版，题目还没有多看。

      今下午和晚上，复习了数位DP，有了更加深入的认识，基础题型是计算一个区间（a，b）符合某个条件的数的个数。一般数位dp是一种暴力枚举的方法。它就是在数位上一位一位的枚举，使得这种枚举方式符合dp的定义，并且使用记忆化搜索，就会节省枚举的时间。换了一个模版，实用性更大，但是不怎么好理解，暂时可以理解个大概：

1. int a[20];  
2. int dp[20][state];  
3.   
4. int dfs(int pos,int zhuangtai,/*这里可能有很多状态*/int limit)  
5. {  
6.     if(pos==-1)return 1;//这里根据情况不一样，返回值不一样  
7.     if(!limit&&dp[pos][state]!=-1/*如果有前导零的题，这里还有前导零的判断*/)return dp[pos][state];  
8.     int sum=0;  
9.     int end=limit?a[pos]:9;//这里是根据这一位数是否应该有限制，设置枚举的最大数，不过这是十进制的  
10.     for(int i=0;i<=end;i++)//循环  
11.     {  
12.         if()....//限制条件。  
13.         sum+=dfs(pos-1,/*状态或者前导零*/limit&&i==a[pos])  
14.           
15.     }  
16.     if(!limit/*有时候有前导零*/)dp[pos][state];  
17.     return sum;  
18.   
19.   
20. }  
21.   
22. int solve(int x)  
23. {  
24.     int pos=0;  
25.     while(x)  
26.     {  
27.         a[pos++]=x%10;  
28.         x/10;  
29.     }//这里是数位分解 
30.     return dfs(pos-1,/*状态限制*/,1);  
31. }  
32. int main()  
33. {  
34.     int q,w;  
35.     while(~scanf("%d%d",&q,&w))  
36.     {  
37.         printf("%d\n",solve(q)-solve(w));  
38.     }  
39.     return 0;  
40. }