hdu 4734 数位dp
HDU DP 数位
2023-09-11 14:20:44 时间
/* 数位dp,记忆化搜索写法 注意memset(dp,-1,sizeof(dp))是放在外面的,这样保证每次搜索时存的值满足下一次也能够用; 假设放在里面就会超时 每一个长度有10000种状态 */ #include<stdio.h> #include<string.h> #define N 20 int len,digit[N],dp[N][10000]; int dfs(int len,int cnt,int ok) { if(cnt<0)return 0; if(!len)return 1; if(!ok&&dp[len][cnt]!=-1) return dp[len][cnt]; int ans=0,i,maxx=ok?digit[len]:9; for(i=0;i<=maxx;i++) ans+=dfs(len-1,cnt-i*(1<<(len-1)),ok&&i==maxx);// if(!ok)//仅仅有当不是边界时才干够存储 dp[len][cnt]=ans;//长度为len时小于等于cnt的值 return ans; } int f(int n,int kk) { int len=0; while(n) { digit[++len]=n%10; n/=10; } return dfs(len,kk,1); } int main() { int t,n,m,k=0,z,kk; scanf("%d",&t); memset(dp,-1,sizeof(dp)); while(t--) { scanf("%d%d",&n,&m); kk=0;z=1; while(n) { kk+=n%10*z; z*=2; n/=10; } printf("Case #%d: %d\n",++k,f(m,kk)); } return 0;}
相关文章
- hdu 3555 Bomb 【数位DP】
- Hdu-1565 方格取数(1) (状态压缩dp入门题
- hdu 1171 Big Event in HDU(01背包)
- HDU 2196 Computer 树形DP经典题
- HDU 4405 Aeroplane chess (概率dp)
- HDU 4897 Little Devil I
- HDU 4436 str2int
- hdu 2767 Proving Equivalences
- HDU 3440 House Man
- HDU 6377 度度熊看球赛 (计数DP)
- HDU 3341 Lost's revenge (AC自动机+DP)
- HDU 4511 小明系列故事——女友的考验 (AC自动机 + DP)
- HDU 1207 汉诺塔II (简单DP)
- HDU 4336 Card Collector (期望DP+状态压缩 或者 状态压缩+容斥)
- HDU 4352 XHXJ's LIS (数位DP+LIS+状态压缩)
- HDU 4734 F(x) (数位DP)
- HDU 2602 Bone Collector (01背包DP)
- HDU 3652 B-number (数位DP)
- HDU 4438 Hunters (数学,概率计算)
- HDU 5444 Elven Postman (二叉树,暴力搜索)
- HDU 3555 Bomb (数位DP)
- HDU 1513 && POJ 1159 Palindrome (DP+LCS+滚动数组)
- HDU 4856 Tunnels(BFS+状压DP)
- !HDU 1078 FatMouse and Cheese-dp-(记忆化搜索)
- HDU-1686-Oulipo(KMP)
- hdu 1506 Largest Rectangle in a Histogram ((dp求最大子矩阵))