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