首页 > 代码库 > FZU 2113（数位dp）
FZU 2113（数位dp）
题目连接：http://acm.hust.edu.cn/vjudge/problem/viewProblem.action?id=38054
题意：求区间[a,b]中包含‘1‘的个数。
分析：数位dp，dp[pos][sum]表示第pos位已包含sum个1时pos后面可以任意填（即！limit时）的状态。
数位dp学习资料：
http://www.cnblogs.com/jffifa/archive/2012/08/17/2644847.html
kuangbin ：http://www.cnblogs.com/kuangbin/category/476047.html
http://blog.csdn.net/cmonkey_cfj/article/details/7798809
http://blog.csdn.net/liuqiyao_01/article/details/9109419
#include <cstdio>#include <cstring>#include <string>#include <cmath>#include <iostream>#include <algorithm>#include <queue>#include <cstdlib>#include <stack>#include <vector>#include <set>#include <map>#define LL long long#define mod 10007#define inf 0x3f3f3f3f#define N 100010#define FILL(a,b) (memset(a,b,sizeof(a)))#define lson l,m,rt<<1#define rson m+1,r,rt<<1|1using namespace std;LL dp[22][22];int dig[22];//pos表示第pos位，sum表示前面已包含1的个数，limit表示后面是否可以任意填LL dfs(int pos,int sum,bool limit){ if(pos==0)return sum; if(!limit&&~dp[pos][sum])return dp[pos][sum]; int len=limit?dig[pos]:9; LL ans=0; for(int i=0;i<=len;i++) { if(i==1)ans+=dfs(pos-1,sum+1,i==len&&limit); else ans+=dfs(pos-1,sum,i==len&&limit); } if(!limit)dp[pos][sum]=ans; return ans;}LL solve(LL x){ int len=0; while(x) { dig[++len]=x%10; x/=10; } LL ans=dfs(len,0,1); return ans;}int main(){ LL a,b; while(cin>>a>>b) { memset(dp,-1,sizeof(dp)); printf("%I64d\n",solve(b)-solve(a-1)); }}
FZU 2113（数位dp）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。