hdu 3652 B-number（数字dp）

http://acm.hdu.edu.cn/showproblem.php?

pid=3652

大致题意：”B-number“即一个整数含有子串”13″且被13整除。求1-n之间这种数的个数。

思路：有两个限制条件：含有子串“13”和能被13整除。

那么设dp[site][mod][flag]。表示到第site位对13取余为mod且标记为flag的数的个数。flag表示是否含有子串”13″。

然后进行记忆话搜索。

#include <stdio.h>
#include <iostream>
#include <map>
#include <stack>
#include <vector>
#include <math.h>
#include <string.h>
#include <queue>
#include <string>
#include <stdlib.h>
#include <algorithm>
#define LL long long
#define _LL __int64
#define eps 1e-8
#define PI acos(-1.0)
using namespace std;

int dp[15][15][5];
int dig[15];
//flag = 0表示前一个不是1，flag = 1表示前一个是1。flag = 2表示出现"13"。
int dfs(int site, int mod, int flag, int up){    if(site == 0)        return mod == 0 && flag == 2; //当mod为0且有"13"时。返回1    if(!up && dp[site][mod][flag] != -1)//记忆化        return dp[site][mod][flag];    int len = up ?
 dig[site] : 9;    int ans = 0;    for(int i = 0; i <= len; i++)    {        int tmod = (mod*10 + i) % 13;        int tflag = flag;        if(flag == 1 && i == 3)            tflag = 2;        else if(flag == 0 && i == 1)            tflag = 1;        else if(flag == 1 && i != 1)            tflag = 0;        ans += dfs(site-1, tmod, tflag, up && (i == len) );    }    if(!up)        dp[site][mod][flag] = ans;    return ans;}int cal(int n){    int cnt = 0;    while(n)    {        dig[++cnt] = n % 10;        n /= 10;    }    memset(dp,-1,sizeof(dp));    return dfs(cnt,0,0,1);}int main(){    int n;    while(~scanf("%d",&n))    {        printf("%d\n",cal(n));    }    return 0;}