LightOJ 1140 计数/数位DP 入门

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

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

/** @Date    : 2016-10-27-17.26

  * @Author  : Lweleth (SoungEarlf@gmail.com)

  * @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
", ++cnt, sol(b) - sol(a - 1));

    }

    return 0;

}

LightOJ 1140 计数/数位DP 入门

相关推荐