1833: [ZJOI2010]count 数字计数

题目:传送门


题解:

   今天是躲不开各种恶心DP了???

   %爆靖大佬啊!!!

   据说是数位DP裸题...emmm学吧学吧

   感觉记忆化搜索特别强:

   定义f[i][j][k]表示若前i个位置有k个j的此时的全局方案数,然后就可以记忆化搜索了(具体看代码吧)

  


代码:

 #include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>
using namespace std;
typedef long long LL;
LL f[][][],a[];
LL n,m;
LL dfs(int pos,int x,int sum,bool ld,bool lt)//ld表示当前情况是否要考虑前导0,lt表示的是枚举数字的上限是否有规定
{
if(pos==)return sum;
if(ld==false && lt==false && f[pos][x][sum]!=-)return f[pos][x][sum];
LL up=,ans=;if(lt==true)up=a[pos];
for(int i=;i<=up;i++)
{
int ss=sum;bool bk1=false,bk2=false;
if(i==x)ss++;
if(ld==true && i==){bk1=true;if(x==)ss--;}
if(lt==true && i==a[pos])bk2=true;
ans+=dfs(pos-,x,ss,bk1,bk2);
}
if(ld==false && lt==false)f[pos][x][sum]=ans;
return ans;
}
LL sol(LL x,int y)
{
int pos=;
while(x){a[++pos]=x%;x/=;}
return dfs(pos,y,,,);
}
int main()
{
memset(f,-,sizeof(f));
scanf("%lld%lld",&n,&m);
for(int i=;i<;i++)printf("%lld ",sol(m,i)-sol(n-,i));
printf("%lld\n",sol(m,)-sol(n-,));
return ;
}

最新文章

  1. Fragment基础----生命周期
  2. 单例模式-C++
  3. 【转】}目前比较全的CSS重设(reset)方法总结
  4. GitHub详解(GitHub for Windows)
  5. HDU2444-The Accomodation of Students-判断是否为二分图+ISAP
  6. CSS权威指南 - 基本视觉格式化 4
  7. Django常用命令及参数配置(Django 1.8.6)
  8. Android 第三方开源库收集整理(转)
  9. Effective Java 58 Use checked exceptions for recoverable conditions and runtime exceptions for programming errors
  10. (转)C++笔记:面向对象编程基础
  11. 【 Android】自定义的AlertDialog中的EditText无法调用输入法问题解决
  12. 自制mpls ldp实验
  13. 初学JSP
  14. js饼状图(带百分比)功能实现,新人必懂
  15. python多线程和多进程
  16. spark之JDBC开发(实战)
  17. 日常英语---十二、MapleStory/Monsters/Level 1-10(Horny Mushroom)
  18. vue todolist待办事项完整
  19. C# 实现IDisposable的模式
  20. python后端工程师 数据爬虫

热门文章

  1. SQLServer2008 使用sql语句访问excel数据
  2. Android Fragment间的广播消息接收
  3. SQL Server之十大存储过程
  4. 《3D建模初步》参考资料
  5. AS3.0+PHP写入mySQL
  6. Python-通过configparser读写配置文件
  7. 查看占用某端口的进程——netstat、findstr 的使用
  8. 团体程序设计天梯赛-练习集-L1-044. 稳赢
  9. 重写servlet,可以获取不同的方法
  10. Lua的string库函数、lua中string的模式匹配