HDU 4734 （数位DP）题解

思路：

dp[pos][pre]代表长度为pos的不大于pre的个数

#include<iostream>

#include<cstdio>

#include<cstring>

#include<string>

#include<queue>

#include<set>

#include<vector>

#include<map>

#include<stack>

#include<cmath>

#include<algorithm>

using namespace std;

const int N = 100+5;

int dp[12][200000],a[20],UP;

int F(int x){

    int ret = 0,pos = 0;

    while(x){

        ret += (x % 10) *(1 << pos);

        pos++;

        x /= 10;

    }

    return ret;

}

int dfs(int pos,int sum,bool limit){

    if(pos == -1) return sum >= 0;

    if(sum < 0) return 0;

    if(!limit && dp[pos][sum] != -1) return dp[pos][sum];

    int top = limit? a[pos] : 9;

    int ret = 0;

    for(int i = 0;i <= top;i++){

        ret += dfs(pos-1,sum-i*(1<<pos),limit && i == top);

    }

    if(!limit) dp[pos][sum] = ret;

    return ret;

}

int solve(int x){

    int pos = 0;

    while(x){

        a[pos++] = x % 10;

        x /= 10;

    }

    return dfs(pos-1,UP,true);

}

int main(){

    int k = 1;

    memset(dp,-1,sizeof dp);

    int A,B;

    int T;

    scanf("%d",&T);

    while(T--){

        scanf("%d%d",&A,&B);

        UP = F(A);

        printf("Case #%d: %d\n",k++,solve(B));

    }

    return 0;

}

巴特西

HDU 4734 （数位DP）题解

最新文章

热门文章