hdu 2089 不要62 （数位dp模板题，附带详细解释）

2016-03-15 · 2 min read · dp 数位dp

题目链接 题意：问区间[n,m]中，不含数字4，也不含数字串“62”的所有数的个数。

思路：可以转化成求区间[0,x]

第一次接触数位dp,参考了这几篇博客。

不要62（数位dp）解题报告

解题报告2

解题报告3

比较重要的前提：

¨对于一个小于n的数，肯定是从高位到低位出现某一位<n的那一位。

¨如 n = 58 n为十进制数。

¨  x = 49 此时x的十位<n

¨  x = 51 此时x的个位<n

¨有了上述性质，我们就可以从高到低枚举第一次<n对应位是哪一位。

这样之前的位确定了，之后的位就不受n的限制即从00...0~99...9，可以先预处理

以及写成递归形式代码会简洁很多，所以就写了递归形式。

更详细的解释参加代码注释。

/* ***********************************************
Author :111qqz
Created Time :2016年03月15日 星期二 18时04分46秒
File Name :code/hdu/2089.cpp
************************************************ */

 1#include <cstdio>
 2#include <cstring>
 3#include <iostream>
 4#include <algorithm>
 5#include <vector>
 6#include <queue>
 7#include <set>
 8#include <map>
 9#include <string>
10#include <cmath>
11#include <cstdlib>
12#include <ctime>
13#define fst first
14#define sec second
15#define lson l,m,rt<<1
16#define rson m+1,r,rt<<1|1
17#define ms(a,x) memset(a,x,sizeof(a))
18typedef long long LL;
19#define pi pair < int ,int >
20#define MP make_pair

1using namespace std;
2const double eps = 1E-8;
3const int dx4[4]={1,0,0,-1};
4const int dy4[4]={0,-1,1,0};
5const int inf = 0x3f3f3f3f;
6int n,m;
7int dp[30][2];
8int digit[30];

1int dfs (int pos,bool preis6,bool limit)  //pos表示从低到高的第几位，是从高位往低位递归的（也就是从左到又）
2					  // preis6 表示上一个数字是否为6，
3					  // limit表示该位置是否有限制。
4{
5//    cout<<pos<<" "<<preis6<<" "<<limit<<" "<<endl;
6    if (pos==0) return 1; //到该位置表明找到了一个解.

1    int res = 0 ;
2    if (!limit&&dp[pos][preis6]!=-1) return dp[pos][preis6];  //如果不是limit位置，表示结果是通用的，而之前又算过的话，就可以直接调用这个结果。
3    int mx = limit?digit[pos]:9; //mx第pos位置能取到的最大的数字..如果不是limit,则可以0..9任意取。
4//    cout<<"mx:"<<mx<<endl;

1    for ( int i = 0 ; i <= mx;  i++)
2    {
3	if (i==4||(i==2&&preis6)) continue;
4	res += dfs(pos-1,i==6,limit&&i==mx); 
5	//(limit&&i==mx)中limit的含义是。。如果当前一位不是limit位（即0..9可以随便取的位置）
6	//，那么之后的位置也一定不是limit位置。
7	//而i==mx部分的意思是，在当前位置的数字小于当前位置的数字能取的最大值（mx）之前，
8	//后面位的数字随便取也不会超过上界。
9    }

    if (!limit) dp[pos][preis6]=res;  //记忆化. 非limit位的结果才通用，不然没必要存。

    return res;

 1}
 2int solve ( int n)
 3{
 4    ms(digit,0);  //将数按照每一位存到digit数组中
 5    int len = 0 ;
 6    while (n)
 7    {
 8	digit[++len] = n % 10;
 9	n/=10;
10    }

    return dfs(len,false,true);

}

1int main()
2{
3	#ifndef  ONLINE_JUDGE 
4	freopen("code/in.txt","r",stdin);
5  #endif

1	while (~scanf("%d %d",&n,&m))
2	{
3	    if (n==0&&m==0) break;

	    ms(dp,-1);
	    int ans = solve (m)-solve(n-1);

	    printf("%d\n",ans);
	}

1  #ifndef ONLINE_JUDGE  
2  fclose(stdin);
3  #endif
4    return 0;
5}