首页 > 代码库 > Hdu3555Bomb数位dp
Hdu3555Bomb数位dp
含有49的 。。就是不要49
。。也可以直接搞
#include <cstdio>#include <cstring>#include <algorithm>#include <climits>#include <string>#include <iostream>#include <map>#include <cstdlib>#include <list>#include <set>#include <queue>#include <stack>#include<math.h>using namespace std;typedef long long LL;LL dp[100][2];LL up[111];LL dfs(LL now,LL pre,LL flag){ if(now==1) return 1; if(!flag&&~dp[now][pre]) return dp[now][pre]; LL limit=flag?up[now-1]:9,ret=0; for(LL i =0 ;i<=limit;i++){ if(i==9&&pre) continue; ret+=dfs(now-1,i==4,flag&&(limit==i)); } return flag? ret: dp[now][pre]= ret;}LL solve(LL x){ LL len=0; while(x){ up[++len]=x%10; x/=10; } return dfs(len+1,0,1);}int main(){ LL n; LL Icase; memset(dp,-1,sizeof(dp)); cin>>Icase; while(Icase--){ cin>>n; LL t1=solve(n); cout<<n-t1+1<<endl; } return 0;}
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。