[Swust OJ 1097]--2014(数位dp)

题目链接：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 10

100 1024

Sample Input

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 ;

 }

巴特西

[Swust OJ 1097]--2014(数位dp)

最新文章

热门文章