首页 > 代码库 > HDU_4734_数位dp

HDU_4734_数位dp

http://acm.hdu.edu.cn/showproblem.php?pid=4734

 

模版题。

 

#include<iostream>#include<cstdio>#include<cstring>using namespace std;int dp[20000][15],a,b,num[15];int dfs(int sum,int pos,int limit){    if(pos == 0)    return sum >= 0;    if(sum < 0)     return 0;    if(!limit && dp[sum][pos] != -1)    return dp[sum][pos];    int ans = 0,endd = limit?num[pos]:9;    for(int i = 0;i <= endd;i++)    {        ans += dfs(sum-i*(1<<(pos-1)),pos-1,limit && i == endd);    }    if(!limit)  dp[sum][pos] = ans;    return ans;}int main(){    memset(dp,-1,sizeof(dp));    int T;    scanf("%d",&T);    for(int i = 1;i <= T;i++)    {        scanf("%d%d",&a,&b);        int sum = 0,now = 1;        while(a)        {            sum += a%10*now;            now *= 2;            a /= 10;        }        now = 1;        while(b)        {            num[now] = b%10;            now++;            b /= 10;        }        printf("Case #%d: %d\n",i,dfs(sum,now-1,1));    }    return 0;}

 

HDU_4734_数位dp