首页 > 代码库 > 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
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。