hdu3555 Bomb --数位dp

原题链接：​​http://acm.hdu.edu.cn/showproblem.php?pid=3555​​

题意：1---n之间的数包含49有多少个。

分析：看代码。

#define _CRT_SECURE_NO_DEPRECATE

#include<iostream>
#include<vector>
#include<cstring>
#include<queue>
#include<stack>
#include<algorithm>
#include<cmath>
#include<string>
#include<stdio.h>
#define INF 99999999
#define eps 0.0001
using namespace std;

typedef long long ll;

int t;
ll n;
ll dp[20][10];//dp[i][j]表示i位数，最高位是j的不含49的个数
int digit[20];

void init()
{
  memset(dp, 0, sizeof(dp));
  dp[0][0] = 1;
  for (int i = 1; i <= 19; i++)
  {
    for (int j = 0; j <= 9; j++)
    {
      for (int k = 0; k <= 9; k++)
        if (!(j == 4 && k == 9))
          dp[i][j] += dp[i - 1][k];
    }
  }
}

ll solve(ll n)//n本身并没有判断是否包含49，所以参数带入是多加了一个1，这点需要注意
{
  memset(digit, 0, sizeof(digit));
  int len = 0;
  ll ans = 0;
  ll num = n;

  while (n)
  {
    digit[++len] = n % 10;
    n /= 10;
  }

  for (int i = len; i >= 1; i--)
  {
    for (int j = 0; j < digit[i]; j++)
    {
      if (!(digit[i + 1] == 4 && j == 9))
        ans += dp[i][j];
    }
    if (digit[i + 1] == 4 && digit[i] == 9)
      break;
  }

  return num - ans;//注意ans求出的不含49的，题意要求[1---n]，这里的参数实际是n+1，且求得是[0--n]，所以读者需要注意
}

int main() 
{
  init();

  scanf("%d", &t);
  while (t--)
  {
    scanf("%lld", &n);
    printf("%lld\n", solve(n + 1));
  }
  return 0;
}