通过这个题对于数位dp中前导0的处理有了新的认识。

题目链接:http://poj.org/problem?id=3252

//http://poj.org/problem?id=3252

#include<cstdio>
#include<cstring>
using namespace std; int b[];
int dp[][][]; int dfs(int pos,int preok,int more,int pre0)
{
if (pos==-) return more==?:;
if (preok && dp[pos][more+][pre0]!=-) return dp[pos][more+][pre0];
int up=preok?:b[pos];
int ans=;
for (int i=;i<=up;i++)
{
if (i<b[pos]||preok) ans+=dfs(pos-,,more+(i==?:pre0-),pre0&&!i);
else ans+=dfs(pos-,,more+(i==?:pre0-),pre0&&!i);
}
if (preok) dp[pos][more+][pre0]=ans;
//printf("pos=%d preok=%d more=%d pre0=%d ans=%d\n",pos,preok,more,pre0,ans);
return ans;
} int solve(int n)
{
if (n<) return ;
int cnt=;
int now=n;
do{
b[cnt]=now%;
now/=;
cnt++;
}while (now);
int ans=;
for (int i=;i<=cnt;i++)
ans+=dfs(cnt-,,i,);
return ans;
} int main()
{
int n,m;
memset(dp,-,sizeof(dp));
while (~scanf("%d%d",&n,&m))
{
printf("%d\n",solve(m)-solve(n-));
}
return ;
}

最新文章

  1. 趣味C程序-HelloWord
  2. angularjs的$filter使用
  3. java基础知识复习
  4. 选择哪种方式进行SharePoint的备份
  5. hdu 4585 map **
  6. vilte/vowifi
  7. @media screen解决移动web开发的多分辨率问题
  8. Delphi-CompareStr 函数
  9. Android的JNI开发
  10. 单机使用tungsten 同步mysql数据到mongodb
  11. Nginx 搭建反向代理服务器过程详解
  12. tableview cell添加3D动画
  13. HTML第一课
  14. cisco linksys ea3500 刷机 openwrt
  15. hadoop集群崩溃,因为tmp下/tmp/hadoop-hadoop/dfs/name文件误删除
  16. SpringBoot系列: 制作Docker镜像的全过程
  17. 爬虫(五)requests模块2
  18. 大数据技术 - 通俗理解MapReduce之WordCount(二)
  19. Servlet注释与部署描述符
  20. oracle 查出一个表中字段值出现次数大于2的所有记录

热门文章

  1. linux下磁盘分区、格式化、挂载
  2. n点游戏
  3. Mysql通过Adjacency List(邻接表)存储树形结构
  4. Vue 去脚手架插件,自动加载vue文件,style怎么办
  5. P1332 血色先锋队
  6. Windows2008新建域时Administrator 帐户密码不符合要求
  7. VS2010安装MVC3出错
  8. 【面试题】2018年最全Java面试通关秘籍第五套!
  9. Python 3基础教程20-Python中导入模块和包
  10. Java 集合学习--ArrayList