手机号码

数位DP模板题

记忆化搜索:

#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
#define int long long
int L,R,Maxx[],dp[][][][][][];
int dfs(int len,bool ok,int last,bool same,bool four,bool eight,bool shangxian)
//剩余的位数,是否已经有三个连续相同的数字,上一个数字,上一个数是否与上上个数字相同,是否有4,是否有8,是否是上限值
{
if(len==) return (int)ok;
if(!shangxian&&dp[len][ok][last][same][four][eight]!=-)
return dp[len][ok][last][same][four][eight];
int M=shangxian?Maxx[len]:,cnt=;
for(int i=;i<=M;i++){
if((four&&i==)||(eight&&i==)||(len==&&i==)) continue;
cnt+=dfs(len-,ok||(same&&last==i),i,last==i,four||i==,eight||i==,shangxian&&i==M);
}
if(!shangxian) dp[len][ok][last][same][four][eight]=cnt;
return cnt;
}
int solve(int x){
int cnt=;
memset(dp,-,sizeof(dp));
while(x){
Maxx[++cnt]=x%;
x/=;
}
return dfs(,,-,,,,);
}
#undef int
int main()
#define int long long
{
scanf("%lld%lld",&L,&R);
int B=solve(L-);
int A=solve(R);
printf("%lld\n",A-B);
return ;
}

最新文章

  1. Python之路第一课Day11--随堂笔记(异步IO\数据库\队列\缓存之二)
  2. [AlwaysOn Availability Groups]AlwaysOn健康诊断日志
  3. 第二十九篇:使用SOUI的SMCListView控件
  4. jboss设置图片上传大小
  5. 如何在mysql中退出当前窗口界面而不关闭窗口的方法
  6. centos6.5 安装
  7. mysql主从复制 详解
  8. poj2955:括号匹配,区间dp
  9. C#外挂QQ
  10. Oracle自动备份数据
  11. MySQL 字符集问题及安全的更新操作
  12. 软件工程第三次作业-结对作业NO.1
  13. Echarts柱状图实现不同颜色渐变色
  14. Android 入门(1)使用第三方控件
  15. bzoj3051[WC2013]平面图(树上倍增+平面图转对偶图+扫描线)
  16. 帮你彻底搞懂JS中的prototype、__proto__与constructor(图解)
  17. double compare 0
  18. awk、sed、grep三大shell文本处理工具之sed的应用
  19. 推荐一个 .Net Core 的 Redis 库
  20. codeforces 434D

热门文章

  1. 使用pygame开发一个弹幕射击游戏(一)
  2. js 中移动元素的方法
  3. 【Ubuntu】ubuntu 16.04 设置root用户初始密码
  4. 系统更新后vs2012无法打开方案资源管理器
  5. mybatis一对多映射
  6. ubuntu下安装MySQL8.0
  7. springboot vue组件写的个人博客系统
  8. 1094 FBI树
  9. 小程序 - 图片列表显示lazyload效果
  10. XUtils3 的 环境搭建与简单使用