hdu2089 不要62--数位dp入门题

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

题意：给定a，b两数，求两数之间所有数不含有62和4的个数。

分析：dp[ i ][ j ]表示i位数，最高位是j的满足题意的个数。

if (cnt[i] == 4 || (cnt[i] == 2 && cnt[i + 1] == 6));
break;

上面的代码你可能有疑问，例如780，现在最高位7,有6_ _，5_ _，4_ _，，，，，，0_ _，但是我们发现7_ _也是存在的，比如779，只要比780小就可以了。好，接下来开始8，有77_，76_，75_，，，，70_，7被固定。你可能会想，提前break结束，比如444，那第一个4做完就退出了，我们只找到了3位数，那2位，1位的呢？请看0_ _这个，它已经包含了。因为最高位前面没有了，所以在做到次最高的时候，并不会造成重复，因为已经做过的位会被固定。

#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;

int dp[10][10];
int l, r;
int cnt[10];

/* 这里算是打表的意思 */
void init()
{
  memset(dp, 0, sizeof(dp));
  dp[0][0] = 1;
  for (int i = 1; i <= 7; i++)//一共i位的数
  {
    for (int j = 0; j < 10; j++)//第i位的数字,从右往左数
    {
      for (int k = 0; k < 10; k++)//第i-1位的数字
      {
        if (!(j == 6 && k == 2) && j != 4)//别写成(j!=6&&k!=2)
          dp[i][j] += dp[i - 1][k];
      }
      //cout << dp[i][j] << " ";
    }
    //cout << endl;
  }
}

int solve(int n)
{
  int ans = 0;
  int num = 0;
  memset(cnt, 0, sizeof(cnt));
  while (n)
  {
    cnt[++num] = n % 10;
    n /= 10;
  }

  for (int i = num; i >= 1; i--)
  {
    for (int j = 0; j < cnt[i]; j++)
    {
      if (!(cnt[i + 1] == 6 && j == 2) && j != 4)
        ans += dp[i][j];
    }
    if (cnt[i] == 4 || (cnt[i] == 2 && cnt[i + 1] == 6));
      break;
  }
  return ans;
}

int main() 
{
  init();

  while (~scanf("%d %d", &l, &r) && (l + r))
  {
    //cout << solve(r + 1) << " " << solve(l) << endl;
    printf("%d\n", solve(r + 1) - solve(l));
  }
  return 0;
}