hdu2098 不要62 ——数位DP入门题

April 15, 2013
Hdu DP

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=2089 题目大意：　　含有4或者62的数字是不吉利数字，给一个区间，[m, n]，求这个区间内的除了不吉利数字以外的数字的数目。思路：　　由于数据范围只有1~1000000，可以暴力，水题，但是为了练习一下数位DP，没有把它当水题做…… 　　看的是这个人的代码：http://blog.csdn.net/acm_cxlove/article/details/7819907# 　　和hdu3555那道题目相似，但是多了一个条件，多了一个不含有4的条件，讨论一下。


#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <stack>
#include <queue>
#include <cmath>
#include <algorithm>
#define lson l, m, rt<<1
#define rson m+1, r, rt<<1|1
using namespace std;
typedef long long int LL;
const int MAXN =  0x3f3f3f3f;
const int  MIN =  -0x3f3f3f3f;
const double eps = 1e-9;
const int dir[8][2] = {{0,1},{1,0},{0,-1},{-1,0},{-1,1},
  {1,1},{1,-1},{-1,-1}};
LL dp[8][3]; int a[8], b[8]; bool flag;
int solve(int k){
  int len = 0; LL temp = k;
  while (k){
    a[++len] = k % 10; k /= 10;
  }
  LL ans = 0; int last = 0; flag = false;
  a[len+1] = 0;
  for (int i = len; i >= 1; --i){
    ans += dp[i-1][2] * a[i];
    if (flag){ans += dp[i-1][0] * a[i];}
    //高位位填4，低位的不管
    if (!flag && a[i] > 4) {ans += dp[i-1][0];}
    // 这一位填6，比它第一位的填2
    if (!flag && a[i] > 6) {ans += dp[i-1][1];}
    // 这一位填4，但是比它高一位的要保证是6，因为上面没有考虑到上一位等于6的情况
    if (!flag && a[i] > 2 && a[i+1] == 6) {ans += dp[i][1];} // 这里很悲剧地写成了dp[i-1][1]我去……
    // 标记一下这个数字本身也是不符合条件的
    if (a[i] == 4 || (a[i]==2&&a[i+1]==6)) flag = true;
  }
  if (flag) ans++; //求的是从1~n的不符合条件的个数，如果端点本身不符合，要加1，就是加上判断数字本身的情况
  // 因为上面的每一种情况都没有考虑到这个数字本身是非幸运数字的情况，所以要加上
  return temp - ans;
}
int main(void){
#ifndef ONLINE_JUDGE
  freopen("hdu2089.in", "r", stdin);
#endif
  int n, m;
  memset(dp, 0, sizeof(dp));
  dp[0][0] = 1;
  for (int i = 1; i < 8; ++i){
    dp[i][0] = dp[i-1][0] * 9 - dp[i-1][1];
    dp[i][1] = dp[i-1][0];
    dp[i][2] = dp[i-1][2] * 10 + dp[i-1][1] + dp[i-1][0];
  }
  while (~scanf("%d%d", &m, &n)){
    if (n+m==0) break;
    LL ans1, ans2;
    ans1 = solve(m-1); // 这个区间范围要注意，要求 m ~ n 所以要把 1 ~ m - 1 和1 ~ n - 1 的求出来
    ans2 = solve(n);
    cout << (ans2 - ans1) << endl;
    //可以输出1到10的solve(i)，这种基本的调试技巧要会，别有错误就去问别人……
  }

  return 0;
}

这种题目关键是要考虑清楚所有的情况，思维要严谨，思路要清晰。

Read more