首页 > 代码库 > [数位dp] hdu 2451 Simple Addition Expression
[数位dp] hdu 2451 Simple Addition Expression
题意:给N,求小于N的数中,三个连续的数相加不进位的数有多少个。
思路:和上题类似,就是不是个位的话,可以放0,1,2,3,个位的话只能放0,1,2。
然后就是边界考虑一下,不能超过当前位。
然后就是边界的判断,不是等于len而是等于当前位。
代码:
#include"cstdlib" #include"cstdio" #include"cstring" #include"cmath" #include"queue" #include"algorithm" #include"iostream" using namespace std; //2014年9月24日15:50:51 __int64 dp[22]; int num[22]; __int64 dfs(int site,int f) { if(site==0) return 1; if(!f&&~dp[site]) return dp[site]; int len; if(site!=1) len=f?min(3,num[site]):3; //注意上限 else len=f?min(2,num[site]):2; __int64 ans=0; for(int i=0;i<=len;i++) ans+=dfs(site-1,f&&i==num[site]); //注意边界判定 if(!f) dp[site]=ans; return ans; } __int64 solve(__int64 x) { int cnt=0; while(x) { num[++cnt]=x%10; x/=10; } return dfs(cnt,1); } int main() { __int64 x; memset(dp,-1,sizeof(dp)); while(scanf("%I64d",&x)!=-1) { printf("%I64d\n",solve(x-1)); } return 0; } //2014年9月24日16:17:25
[数位dp] hdu 2451 Simple Addition Expression
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。