bzoj 4521 [Cqoi2016]手机号码——数位dp
2024-09-06 11:57:47
题目:https://www.lydsy.com/JudgeOnline/problem.php?id=4521
dfs真好用~
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define ll long long
using namespace std;
const int N=;
int dg[N];
ll l,r,dp[N][][N][][][];
ll dfs(int p,int len,int lst,bool p0,bool p1,bool ok,bool fx)
{
if(!p){return ok&(!(p0&p1));}
if(!fx&&dp[p][len][lst][p0][p1][ok]!=-)return dp[p][len][lst][p0][p1][ok];
int st=;if(p==)st=;
int end=;if(fx)end=dg[p];
ll ret=;
for(int i=st;i<=end;i++)
{
int lenn=;if(i==lst)lenn=len+;
if(lenn>)lenn=;
ret+=dfs(p-,lenn,i,p0|(i==),p1|(i==),ok|(lenn==),fx&(i==dg[p]));
}
if(!fx)dp[p][len][lst][p0][p1][ok]=ret;
return ret;
}
ll calc(ll x)
{
if(x<1e10)return ;
for(int i=;i<=;i++)dg[i]=x%,x/=;
memset(dp,-,sizeof dp);
return dfs(,,,,,,);
}
int main()
{
scanf("%lld%lld",&l,&r);
printf("%lld\n",calc(r)-calc(l-));
return ;
}
最新文章
- Java基础-重写System.out.println方法
- InnoDB 存储引擎的锁机制
- Java深入 - Java 内存分配和回收机制
- 身份证号码自动生成程序(Python)
- Android中的CharSequence和String
- CSS控制文本超出指定宽度后用省略号代替,CSS控制文本不换行
- thinkphp 3+ 观后详解 (2)
- 3C Tic-tac-toe
- Identity 验证,Authorize 特性
- setTimeout的若干坑
- poj2486 Apple Tree (树形dp)
- POJ 2411
- Spark技术内幕: 如何解决Shuffle Write一定要落盘的问题?
- 导入项目 idea
- 单元测试-unittest模块
- Ubuntu中通过SuperVisor添加守护进程
- mysql字符函数
- python日期加减法操作
- MVC 多submit
- ORB feature(O for orientation)