LightOJ 1140 计数/数位DP 入门

**题意：** 给出a,b求区间a,b内写下过多少个零
**题解：**计数问题一般都会牵扯到数位DP，DP我写的少，这道当作入门了，DFS写法有固定的模板可套用

dp[p][count] 代表在p位 且前面出现过count个零的方案数

/** @Date    : 2016-10-27-17.26
  * @Author  : Lweleth ([e-mail])
  * @Link    : 
  * @Version : $
  */
#include <stdio.h>
#include <iostream>
#include <string.h>
#include <algorithm>
#include <utility>
#include <vector>
#include <map>
#include <set>
#include <string>
#include <stack>
#include <queue>
#define LL long long
#define MMF(x) memset((x),0,sizeof(x))
#define MMI(x) memset((x), INF, sizeof(x))
using namespace std;

const int INF = 0x3f3f3f3f;
const int N = 1e5+2000;

int dp[25][25];
LL bit[25];

//位置 前面零的数量 是否是数的最后一位 是否是零
LL dfs(int p, int cnt, int ima, int ipz)
{
    //if(p == -1)
     //system("pause");
    //cout << p << endl;
    if(p == 0)
        return cnt;
    if(!ima && dp[p][cnt] != -1 && !ipz)
        return dp[p][cnt];

    int len = ima?bit[p]:9;
    LL ans = 0;
    for(int i = 0; i <= len; i++)
    {
        int t = cnt;
        if(i == 0 && !ipz)//注意当前是零时 且前面没有前导零
            t++;
        ans+=dfs(p-1, t, ima && i == len, ipz && i == 0);

    }
    if(!ima && !ipz)
        dp[p][cnt] = ans;
    //cout << ans << endl;
    return ans;
}

LL sol(LL x)
{
    if(x == -1)//考虑a是0的情况
        return -1;
    int len = 0;
    while(x)
    {
        bit[++len] = x % 10;
        x /= 10;
    }
    return dfs(len, 0, 1, 1);
}




int main()
{
    int T;
    cin >> T;
    int cnt = 0;
    while(T--)
    {
        LL a, b;
        scanf("%lld%lld", &a, &b);
        memset(dp, -1, sizeof(dp));
        printf("Case %d: %lld\n", ++cnt, sol(b) - sol(a - 1));
    }
    return 0;
}