题目链接：http://acm.swust.edu.cn/problem/1097/
Time limit(ms): 1000 Memory limit(kb): 32768
今年是2014年，所以小明喜欢2014的每一位数字（即：2,0,1,4）,小明想知道在区间[l，r](包括l和r)中有多少个数中含有这4个数字（数字无前缀零）。
Description
多组数据。
每组数据输入2个数l，r（0<l<r<=10^9）
Input
输出占一行，即区间[l，r]（包括l和r）中包含的满足条件的数的个数
Output
|
1
2
3
|
1 10
100 1024
|
Sample Input
|
1
2
3
|
1
|
Sample Output
输出换行请使用\r\n
Hint
swust第10届校赛
解题思路：就一个简单的数位dp，直接套模板就是了~~~
（不会的可以戳戳这里：http://www.cnblogs.com/zyxStar/p/4563830.html）
代码如下：
#include<iostream>
#include<cstring>
using namespace std;
int dp[][][][][];//返回各数状态
int bit[]; //数位dp
int dfs(int pos, int s2, int s0, int s1, int s4, bool limit, bool fzero)
{
//注意前导零的影响
if (pos == -) return s2&&s0&&s1&&s4;
if (!limit&&!fzero&&~dp[pos][s2][s0][s1][s4])
return dp[pos][s2][s0][s1][s4];//条件判断
int end = limit ? bit[pos] : ;
int ans = , i;
for (i = ; i <= end; i++){
int now2 = s2, now0 = s0, now1 = s1, now4 = s4;
if (s2 == ){
if (i == )
now2 = ;
}
if (s0 == ){
if (!fzero&&i == )
now0 = ;
}
if (s1 == ){
if (i == )
now1 = ;
}
if (s4 == ){
if (i == )
now4 = ;
}
ans += dfs(pos - , now2, now0, now1, now4, limit&&i == end, fzero&&!i);
}
return limit || fzero ? ans : dp[pos][s2][s0][s1][s4] = ans;
}
int calc(int n){
int len = ;
while (n){
bit[len++] = n % ;
n /= ;
}
return dfs(len - , , , , , , );
}
int main(){
int l, r;
memset(dp, -, sizeof(dp));
while (cin >> l >> r)
cout << calc(r) - calc(l - ) << "\r\n";
return ;
}