数位DP，一句话概括，就是在一个给定区间内求出满足某中奇葩条件的数字个数，这真是奇葩题目，但是总体写起来又有一定规律性。
主要可以分为以下几个步骤：

确定主体框架，确定一个大方向，想想该如何设计状态；
下面基本就是模板，直接DFS就行了，一位一位处理，这也是他叫按位DP的原因。
数位DP代码一般都很短，不过效率挺好，解决一些竞赛中出现的问题非常有用 。

如果看了这部分 ，你感觉还是不会的话，(这是当然啊，狂汗~~）,那么请继续往下看。
下面用几个例子来说明一下，具体注释都附在代码内：

PS：我是菜狗，这些都是很水的数位DP，求大神勿喷~~

————————————————————— ——华丽的分割线—————————————————————


Problem 1160 - 科协的数字游戏I
Time Limit: 1000MS       Memory Limit: 65536KB       Difficulty:     
Total Submit: 181      Accepted: 29      Special Judge: No 

Description

科协里最近很流行数字游戏。某人命名了一种不降数，这种数字必须满足从左到右各位数字成大于等于的关系，如123，446。现在大家决定玩一个游戏，指定一个整数闭区间[a,b]，问这个区间内有多少个不降数。

Input

题目有多组测试数据。每组只含2个数字a, b (1 <= a, b <= 2^31)。

Output

每行给出一个测试数据的答案，即[a, b]之间有多少阶梯数。

Sample Input

1 9 
1 19

Sample Output

9
18

Hint

 

[cpp]  view plain copy
  1. /******************************************************************** 
  2. * Problem:科协的数字游戏2 
  3. * source:XDOJ 
  4. * author：sgx 
  5. * date：2013/09/15 
  6. *********************************************************************/  
  7. #include<cstdio>  
  8. #include<cstring>  
  9. #include<algorithm>  
  10.   
  11. using namespace std;  
  12.   
  13. #define LL long long  
  14.   
  15. const int N=25;  
  16. int digit[N];  
  17. LL dp[N][N];  
  18.   
  19. LL dfs(int pos,int statu,int limit)  
  20. {  
  21.      int i,end,s;  
  22.      LL res=0;  
  23.      if(pos==-1)  
  24.         return 1;  
  25.      if(!limit&&dp[pos][statu]!=-1)  
  26.         return dp[pos][statu];  
  27.   
  28.      end=limit?digit[pos]:9;  
  29.      for(i=statu;i<=end;i++)  
  30.          res+=dfs(pos-1,i,limit&&i==end);  
  31.      if(!limit)  
  32.          dp[pos][statu]=res;  
  33.     return res;  
  34. }  
  35.   
  36. LL calc(LL n)  
  37. {  
  38.      int len=0;  
  39.      memset(dp,-1,sizeof(dp));  
  40.      while(n)  
  41.      {  
  42.          digit[len++]=n%10;  
  43.          n/=10;  
  44.      }  
  45.      return dfs(len-1,0,1);  
  46. }  
  47.   
  48. int main()  
  49. {  
  50.      LL a,b;  
  51.      while(scanf("%lld %lld",&a,&b)!=EOF)  
  52.          printf("%lld\n",calc(b)-calc(a-1));  
  53.     return 0;  
  54. }  


 

————————————————————————————————————分割线—————————————————————————————————————

Problem 1161 - 科协的数字游戏II

Time Limit : 1000MS       Memory Limit : 65536KB       Difficulty :     
 Total Submit : 108      Accepted : 13      Special Judge : No 
Description

由于科协里最近真的很流行数字游戏。（= =！汗一个）某人又命名了一种取模数，这种数字必须满足各位数字之和 mod N为0。现在大家又要玩游戏了，指定一个整数闭区间[a,b]，问这个区间内有多少个取模数。

Input
题目有多组测试数据。每组只含3个数字a, b, n (1 <= a, b <= 2^31,1 <= n < 100)。
Output
每个测试用例输出一行，表示各位数字和 mod N为0 的数的个数。
Sample Input
1 19 9
Sample Output
2
Hint

Source
tclh123

 

 

[cpp]  view plain copy
  1. /******************************************************************** 
  2. * Problem:科协的数字游戏2 
  3. * source:XDOJ 
  4. * 分析：记忆化搜索部分，pre表示前面各位数字之和对该数取模的结果 
  5. * author：sgx 
  6. * date：2013/09/15 
  7. *********************************************************************/  
  8. #include <iostream>  
  9. #include <cstdlib>  
  10. #include <cstring>  
  11. #include <cstdio>  
  12.   
  13. using namespace std;  
  14.   
  15. typedef long long LL;  
  16. const int maxn=100+5;  
  17.   
  18. int dp[maxn][105];  
  19. int digit[maxn];  
  20.   
  21. int mod,l,r;  
  22. int DFS(int pos,int pre,bool limit)  
  23. {  
  24.     if(pos==-1)  
  25.         return pre==0;  
  26.     if(!limit&&dp[pos][pre]!=-1)  
  27.         return dp[pos][pre];  
  28.   
  29.      LL res=0,end=limit?digit[pos]:9;  
  30.   
  31.      for(int i=0;i<=end;i++)  
  32.      {  
  33.         int new_pre=(pre+i)%mod;  
  34.          res+=DFS(pos-1,new_pre,limit&&i==end);  
  35.      }  
  36.      if(!limit)  
  37.          dp[pos][pre]=res;  
  38.     return res;  
  39. }  
  40.   
  41. LL solve(int n)  
  42. {  
  43.      int len=0;  
  44.      while(n)  
  45.      {  
  46.          digit[len++]=n%10;  
  47.          n/=10;  
  48.      }  
  49.      return DFS(len-1,0,true);  
  50. }  
  51.   
  52. int main()  
  53. {  
  54.      while(scanf("%d%d%d",&l,&r,&mod)!=EOF)  
  55.      {  
  56.          memset(dp,-1,sizeof(dp));  
  57.          printf("%lld\n",solve(r)-solve(l-1));  
  58.      }  
  59.      return 0;  
  60. }  


 


————————————分割线————————

HDU3052--B-number

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 1556    Accepted Submission(s): 852
Problem Description

A wqb-number, or B-number for short, is a non-negative integer whose decimal form contains the sub- string "13" and can be divided by 13. For example, 130 and 2613 are wqb-numbers, but 143 and 2639 are not. Your task is to calculate how many wqb-numbers from 1 to n for a given integer n.
Input
Process till EOF. In each line, there is one positive integer n(1 <= n <= 1000000000).
Output
Print each answer in a single line.
Sample Input
13
100
200
1000
Sample Output
1
1
2
2

 

 

[cpp]  view plain copy
  1. /************************************************************** 
  2. * 题意：求[1,n]内有多少个数字，该数字有13，且能被13整除 n<=10^9 
  3. 即要满足x % 13 = 0；x=pre*10^pos+next; 
  4.  (pos代表处理到当前的位数，next代表正在处理的位置上面的数字) 
  5.  (pre*10^pos + next) % 13 = 0，pre是之前确定的部分； 
  6.  需要的参数为pre , pos ,状态用status表示 
  7. status==2记录pre拥有"13"，status==1是表示没有出现13，但是首位是1； 
  8. status=0表示没有13； 
  9.  
  10. * Author:sgx 
  11. * Date:2013/09/15 
  12. *************************************************************************/  
  13.   
  14. #include <iostream>  
  15. #include <cstdlib>  
  16. #include <cstring>  
  17. #include <cstdio>  
  18.   
  19. using namespace std;  
  20.   
  21. typedef long long LL;  
  22. const int maxn=100+5;  
  23.   
  24. int dp[10][13][3];  
  25. int digit[10];  
  26.   
  27. int DFS(int pos,int status,int pre,bool limit)  
  28. {  
  29.     if(pos==-1)  
  30.         return status==2&&pre==0;  
  31.     if(!limit&&dp[pos][pre][status]!=-1)  
  32.         return dp[pos][pre][status];  
  33.   
  34.      LL res=0;  
  35.      int end=limit?digit[pos]:9;  
  36.   
  37.      for(int i=0;i<=end;i++)  
  38.      {  
  39.         int new_pre=(pre*10+i)%13;  
  40.         int new_status=status;  
  41.   
  42.         /*准备计算出下一阶段中新的状态status*/  
  43.         if(status==0&&i==1)  
  44.              new_status=1;/*原来没有出现13但是当前位是1，所以属于状态1对应的情况，故更新新状态为1；*/  
  45.         if(status==1&&i==1)  
  46.              new_status=1;/*解释方法同上*/  
  47.         else if(status==1&&i!=3)  
  48.              new_status=0;  
  49.         if(status==1&&i==3)  
  50.              new_status=2;  
  51.   
  52.         res+=DFS(pos-1,new_status,new_pre,limit&&i==end);  
  53.         /*//limit==true则说明有限制,即所有可能并没有被全部记录,故此时记入dp数组 */  
  54.         //limit==false则说明之后的分支状态已经搜索完全  
  55.     }  
  56.     if(!limit)  
  57.          dp[pos][pre][status]=res;  
  58.     return res;  
  59. }  
  60.   
  61. LL solve(int n)  
  62. {  
  63.      int len=0;  
  64.      while(n)  
  65.      {  
  66.          digit[len++]=n%10;  
  67.          n/=10;  
  68.      }  
  69.      return DFS(len-1,0,0,true);  
  70. }  
  71.   
  72. int main()  
  73. {  
  74.      LL m,n;  
  75.      while(scanf("%lld",&n)!=EOF)  
  76.      {  
  77.          memset(dp,-1,sizeof(dp));  
  78.          printf("%lld\n",solve(n));  
  79.      }  
  80.      return 0;  
  81. }  


 

HDU3555----BombTime Limit: 2000/1000 MS (Java/Others)    Memory Limit: 131072/65536 K (Java/Others)
Total Submission(s): 4594    Accepted Submission(s): 1601
Problem Description

The counter-terrorists found a time bomb in the dust. But this time the terrorists improve on the time bomb. The number sequence of the time bomb counts from 1 to N. If the current number sequence includes the sub-sequence "49", the power of the blast would add one point.
Now the counter-terrorist knows the number N. They want to know the final points of the power. Can you help them?
Input
The first line of input consists of an integer T (1 <= T <= 10000), indicating the number of test cases. For each test case, there will be an integer N (1 <= N <= 2^63-1) as the description.

The input terminates by end of file marker.
Output
For each test case, output an integer indicating the final points of the power.
Sample Input
3
1
50
500
Sample Output
0
1
15

 

 

[cpp]  view plain copy
  1. /****************************************************************** 
  2. * PS:网上大神的文章真的太神了，改不了，贴过来 
  3. * 附个链接：http://blog.csdn.net/whyorwhnt/article/details/8764955 
  4. *******************************************************************/  
  5. #include <cstdio>  
  6. #include <cstring>  
  7.   
  8. using namespace std;  
  9.   
  10. int bit[25];  
  11. __int64 dp[25][3];  
  12. //dp[i][0]表示长度为i,没有49  
  13. //dp[i][1]表示长度为i,没有49但前一位为4  
  14. //dp[i][2]表示长度为i,包括49的个数  
  15.   
  16. /*limit表示是否有上限,比如n=1234,现在转移到12,如果下一位选3,那么再下一位就有上限, 
  17. 上限为4,如果不选3,那么下一位就没限制,最高位9,转移能保证转移到数比n小*/  
  18.   
  19. __int64 Dfs (int pos,int s,bool limit) //s为之前数字的状态  
  20. {  
  21.      if (pos==-1)  
  22.         return s==2;  
  23.      if (limit==false && ~dp[pos][s])  
  24.         return dp[pos][s];  
  25.      int i ,end=limit?bit[pos]:9;  
  26.       __int64 ans=0;  
  27.      for (i=0;i<=end;i++)  
  28.      {  
  29.         int nows=s;  
  30.         if(s==0 && i==4)  
  31.              nows=1;  
  32.         if(s==1 && i!=9) //前一位为4  
  33.              nows=0;  
  34.         if(s==1 && i==4)  
  35.              nows=1;  
  36.         if(s==1 && i==9) //49  
  37.              nows=2;  
  38.          ans+=Dfs(pos-1 , nows , limit && i==end);  
  39.      }  
  40.     //limit==true则说明有限制,即所有可能并没有被全部记录,故此时记入dp数组  
  41.     //limit==false则说明之后的分支状态已经搜索完全  
  42.     return limit?ans:dp[pos][s]=ans;  
  43. }  
  44.   
  45. int main ()  
  46. {  
  47.       __int64 n;  
  48.      int T;  
  49.      memset(dp,-1,sizeof(dp));  
  50.      scanf("%d",&T);  
  51.      while (T--)  
  52.      {  
  53.          scanf("%I64d",&n);  
  54.          int len=0;  
  55.          while (n)  
  56.          {  
  57.              bit[len++]=n%10;  
  58.              n/=10;  
  59.          }  
  60.          printf("%I64d\n",Dfs(len-1,0,1));  
  61.      }  
  62.      return 0;  
  63. }  

 

HDU2089--不要62
Time Limit: 1000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 13687    Accepted Submission(s): 4402
Problem Description

杭州人称那些傻乎乎粘嗒嗒的人为62（音：laoer）。
杭州交通管理局经常会扩充一些的士车牌照，新近出来一个好消息，以后上牌照，不再含有不吉利的数字了，这样一来，就可以消除个别的士司机和乘客的心理障碍，更安全地服务大众。
不吉利的数字为所有含有4或62的号码。例如：
62315 73418 88914
都属于不吉利号码。但是，61152虽然含有6和2，但不是62连号，所以不属于不吉利数字之列。
你的任务是，对于每次给出的一个牌照区间号，推断出交管局今次又要实际上给多少辆新的士车上牌照了。
Input
输入的都是整数对n、m（0<n≤m<1000000），如果遇到都是0的整数对，则输入结束。
Output
对于每个整数对，输出一个不含有不吉利数字的统计个数，该数值占一行位置。
Sample Input
1 100
0 0
Sample Output
80


 

[cpp]  view plain copy
  1. /******************************************************************** 
  2. * Problem:HDU2089-不要62 
  3. * source:HDU 
  4. * 分析：记忆化搜索部分，i==4时要及时continue掉，不然无限WA； 
  5. * author：sgx 
  6. * date：2013/09/15 
  7. *********************************************************************/  
  8. #include <iostream>  
  9. #include <cstdlib>  
  10. #include <cstring>  
  11. #include <cstdio>  
  12.   
  13. using namespace std;  
  14.   
  15. typedef long long LL;  
  16. const int maxn=100+5;  
  17.   
  18. int dp[maxn][3];  
  19. int digit[maxn];  
  20. //dp[i][0]表示长度为i,没有62  
  21. //dp[i][1]表示长度为i,没有62但前一位为6  
  22. //dp[i][2]表示长度为i,包括62的个数  
  23. int DFS(int pos,int status,bool limit)  
  24. {  
  25.     if(pos==-1)  
  26.         return status==2;  
  27.     if(!limit&&dp[pos][status]!=-1)  
  28.         return dp[pos][status];  
  29.   
  30.      LL res=0,end=limit?digit[pos]:9;  
  31.   
  32.      for(int i=0;i<=end;i++)  
  33.      {  
  34.         int new_status=status;  
  35.   
  36.         if(i==4)  
  37.              new_status=2;  
  38.         else if(status==0&&i==6)  
  39.              new_status=1;  
  40.         else if(status==1&&i==6)  
  41.              new_status=1;  
  42.         else if(status==1&&i!=2)  
  43.              new_status=0;  
  44.         else if(status==1&&i==2)  
  45.              new_status=2;  
  46.   
  47.          res+=DFS(pos-1,new_status,limit&&i==end);  
  48.      }  
  49.      if(!limit)  
  50.          dp[pos][status]=res;  
  51.      return res;  
  52. }  
  53.   
  54. LL solve(int n)  
  55. {  
  56.      int len=0;  
  57.      while(n)  
  58.      {  
  59.          digit[len++]=n%10;  
  60.          n/=10;  
  61.      }  
  62.     return DFS(len-1,0,true);  
  63. }  
  64.   
  65. int main()  
  66. {  
  67.      int n,m;  
  68.      while(scanf("%d%d",&n,&m)!=EOF&&(n+m))  
  69.      {  
  70.          memset(dp,-1,sizeof(dp));  
  71.          printf("%lld\n",m-n+1-solve(m)+solve(n-1));  
  72.      }  
  73.      return 0;  
  74. }  

 

 

HDU4734F(x)
Time Limit: 1000/500 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 485    Accepted Submission(s): 179
Problem Description

For a decimal number x with n digits (A nA n-1A n-2 ... A 2A 1), we define its weight as F(x) = A n * 2 n-1 + A n-1 * 2 n-2 + ... + A 2 * 2 + A 1 * 1. Now you are given two numbers A and B, please calculate how many numbers are there between 0 and B, inclusive, whose weight is no more than F(A).
Input
The first line has a number T (T <= 10000) , indicating the number of test cases.
For each test case, there are two numbers A and B (0 <= A,B < 10 9)
Output
For every case,you should output "Case #t: " at first, without quotes. The  t is the case number starting from 1. Then output the answer.
Sample Input
3
0 100
1 10
5 100
Sample Output
Case #1: 1
Case #2: 2
Case #3: 13

[cpp]  view plain copy
  1. #include <cstdio>  
  2. #include <cstring>  
  3. #include <iostream>  
  4. #include <cstdlib>  
  5. #include <algorithm>  
  6.   
  7. using namespace std;  
  8.   
  9. const int maxn=300;  
  10. const int maxm=6000;  
  11.   
  12. int dp[maxn][maxm];  
  13. int a[maxn];  
  14.   
  15. int DFS(int pos,int cur,int limit)  
  16. {  
  17.     int i,ed,s,ans=0;  
  18.     if(pos==-1)  
  19.         return cur>=0;  
  20.     if(!limit&&dp[pos][cur]!=-1)  
  21.         return dp[pos][cur];  
  22.   
  23.      ed=limit?a[pos]:9;  
  24.      for(i=0;i<=ed;i++)  
  25.      {  
  26.          s=cur-i*(1<<pos);  
  27.         if(s<0)  
  28.             break;  
  29.          ans+=DFS(pos-1,s,limit&&i==ed);  
  30.      }  
  31.   
  32.      if(!limit&&dp[pos][cur]==-1)  
  33.          dp[pos][cur]=ans;  
  34.      return ans;  
  35. }  
  36.   
  37. int transfer(int n)  
  38. {  
  39.      int res=0,m=1;  
  40.      while(n)  
  41.      {  
  42.          res+=(n%10)*m;  
  43.          n/=10;  
  44.          m*=2;  
  45.      }  
  46.      return res;  
  47. }  
  48.   
  49. int solve(int n,int m)  
  50. {  
  51.      int st=-1;  
  52.      while(m)  
  53.      {  
  54.          a[++st]=m%10;  
  55.          m/=10;  
  56.      }  
  57.      int res=DFS(st,transfer(n),1);  
  58.      return res;  
  59. }  
  60.   
  61. int main()  
  62. {  
  63.      int test,n,m;  
  64.      scanf("%d",&test);  
  65.      memset(dp,-1,sizeof(dp));  
  66.      for(int ii=1;ii<=test;ii++)  
  67.      {  
  68.          scanf("%d%d",&n,&m);  
  69.          printf("Case #%d: %d\n",ii,solve(n,m));  
  70.      }  
  71.      return 0;  
  72. }  


 

windy数 

Description

windy定义了一种windy数。
不含前导零且相邻两个数字之差至少为2的正整数被称为windy数。
windy想知道，在A和B之间，包括A和B，总共有多少个windy数？

Input

包含两个整数，A B。
满足 1 <= A <= B <= 2000000000 。

Output

包含一个整数：闭区间[A,B]上windy数的个数。

Sample Input

1 10


Sample Output

9 

[cpp]  view plain copy
  1. 艰难AC。。。。
[cpp]  view plain copy
  1. <pre class="cpp" name="code">/******************************************************************* 
  2. * problem:windy数 
  3. * source:UESTC1307 
  4. * author:sgx 
  5. * date:2013/09/18 
  6. ********************************************************************/  
  7. #include <iostream>  
  8. #include <cstdio>  
  9. #include <cstring>  
  10. #include <cmath>  
  11.   
  12. using namespace std;  
  13. const int maxn=20;  
  14.   
  15. typedef long long LL;  
  16. LL dp[maxn][11];  
  17. LL digit[maxn];  
  18.   
  19. LL DFS(int pos,int pre,bool limit,bool first_place)//first_place判断前导0  
  20. {  
  21.     if(pos==-1)  
  22.         return first_place==0;  
  23.     if(!limit&&dp[pos][pre]!=-1&&first_place==false)  
  24.         return dp[pos][pre];  
  25.   
  26.      int end=limit?digit[pos]:9;  
  27.      LL ans=0;  
  28.   
  29.      for(int i=0;i<=end;i++)  
  30.      {  
  31.         if(first_place!=0)  
  32.              ans+=DFS(pos-1,i,limit&&i==end,first_place&&i==0);  
  33.         else if(abs(i-pre)>=2)  
  34.              ans+=DFS(pos-1,i,limit&&i==end,first_place);  
  35.      }  
  36.      if(!limit&&first_place==false)  
  37.          dp[pos][pre]=ans;  
  38.      return ans;  
  39. }  
  40.   
  41. LL solve(LL n)  
  42. {  
  43.      LL len=0;  
  44.      while(n)  
  45.      {  
  46.          digit[len++]=n%10;  
  47.          n/=10;  
  48.      }  
  49.      return DFS(len-1,0,true,true);  
  50. }  
  51.   
  52.   
  53. int main()  
  54. {  
  55.   
  56.      LL l,r;  
  57.      while(scanf("%lld%lld",&l,&r)!=EOF)  
  58.      {  
  59.          memset(dp,-1,sizeof(dp));  
  60.          LL ans=solve(r)-solve(l-1);  
  61.          printf("%lld\n",ans);  
  62.      }  
  63.      return 0;  
  64. }