poj 2089 數位DP

• 題意：給你一個區間，求這個區間内所有滿足不含數字2，不含連續數字62的數字的個數。（本題核心思想見代碼注解）
• 題并非水，然而大部分人還是水過的，對1到10,000,000内數字轉化為字元串打表處理即可水過。然而做這個題主要是為了掌握數位DP。

數位DP常見知識點：

• 求區間[l, r]之間的數常常轉化為求區間[0 ,r] - [0, l]之間的數，因為l，r上界下界并不好做。
• 數位DP的核心就是無後效性導緻的減少計算量，展現在這個題中就是，一個j開頭的i位數（定義為 (i,j) )隻與 (i−1,k) 有關。

本題代碼：

#include <set>
#include <map>
#include <cmath>
#include <stack>
#include <queue>
#include <string>
#include <vector>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long int LL;
const int M = 100009,INF = 0x3fffffff;
int f[8][10];

int doit(int x) {  //計算0到x之間有多少個合法數字
    int ans = 0;

    //将x放到一個digital數組，且數組的第i位表示從右向左數x的第i位數字（注意這裡儲存的是char型，後期應該轉化為int來比較
    char d[8], digital[8];;
    sprintf(d, "%d", x);
    int len = strlen(d);
    for (int i = len; i >= 1; i--) {
        digital[i] = d[len - i];
    }
    digital[len + 1] = '\0';

    //這段代碼需要寫出樣例才容易了解，其中用到了幾點性質高位不邊的情況下低位的個數與高位無關
    //如：34xx與4xx與xx(00 to 99) 是一樣的
    for (int i = len; i >= 1; i--) {
        for (int j = 0; j < digital[i] - '0'; j++) {
            if(j != 4 && !(j == 2 && digital[i + 1] == '6')) ans += f[i][j];
        }
        if (digital[i] == '4' || (digital[i] == '2' && digital[i + 1] == '6')) break;
    }
    return ans;
}

int main(void) {
    //problem:hdu 2089 , address:http://acm.hdu.edu.cn/showproblem.php?pid=2089
    int n, m;
    memset(f, 0, sizeof(f));

    /*
    *f[i][j]代表以j開頭長度為i的數字含有合法數字的個數，由于最多相連的兩位數相關，即“62”的情況
    *是以每次更新隻需枚舉兩位數的100種情況。
    */
    f[0][0] = 1;
    for (int i = 1; i <= 7; i++) {
        for (int j = 0; j <= 9; j++) {
            for (int k = 0; k <= 9; k++) {
                if(j != 4 && !(j == 6 && k == 2)) f[i][j] += f[i - 1][k];
            }
        }
    } 
    while(cin >> n >> m && (n || m)) {
        cout << doit(m + 1) - doit(n) << endl;
    }
    return 0;
}