题目描述

windy定义了一种windy数。不含前导零且相邻两个数字之差至少为2的正整数被称为windy数。 windy想知道,

在A和B之间,包括A和B,总共有多少个windy数?

输入输出格式

输入格式:

包含两个整数,A B。

输出格式:

一个整数

数位DP,记录每一位最后一位是什么,枚举时如果他们的差小于2就return。

但是注意!如果有前导零,也就是00014是一个合法的序列,但是一般会判断1和0差小于2,就算非法了。

我们需要记录前导零,如果当前是前导零,则默认当前位位-10000,也就是下一位随便取。

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstdlib>
#include <cstring>
#define in(a) a=read()
#define REP(i,k,n) for(int i=k;i<=n;i++)
using namespace std;
inline int read(){
int x=,f=;
char ch=getchar();
for(;!isdigit(ch);ch=getchar())
if(ch=='-')
f=-;
for(;isdigit(ch);ch=getchar())
x=x*+ch-'';
return x*f;
}
int a,b,digit[],dp[][],ind;
inline int dfs(int pos,int state,bool ze,bool flag){
if(!pos) return ;
if(!ze && dp[pos][state] && !flag) return dp[pos][state];
int up,ans=;
if(flag) up=digit[pos];
else up=;
REP(i,,up){
if(abs(i-state)<) continue;
if(ze && !i) ans+=dfs(pos-,-,,flag && i==digit[pos]);
else ans+=dfs(pos-,i,,flag && i==digit[pos]);
}
if(!flag && !ze) dp[pos][state]=ans;
return ans;
}
inline int solve(int x){
ind=;
while(x){
digit[++ind]=x%;
x/=;
}
memset(dp,,sizeof(dp));
return dfs(ind,-,,);
}
int main(){
in(a),in(b);
printf("%d",solve(b)-solve(a-));
}

最新文章

  1. 初学者看过来之JSON入门
  2. 对ASP.NET 5和ASP.NET MVC 6应用程序进行集成测试
  3. Android5.0版本之后切换听筒模式
  4. poj 3358 Period of an Infinite Binary Expansion
  5. HDU-1037(水水水题)
  6. 3proxy 二级代理配置样例
  7. A Statistical View of Deep Learning (IV): Recurrent Nets and Dynamical Systems
  8. BZOJ 3390: [Usaco2004 Dec]Bad Cowtractors牛的报复
  9. C 实现基于角色的权限系统
  10. 第十四章——循环神经网络(Recurrent Neural Networks)(第一部分)
  11. java中的BigDecimal和String的相互转换,int和String的类型转换,Integer类和String相互转换
  12. 二、linux IO 编程---系统调用和POSIX标准和标准IO
  13. spring整合Jersey 无法注入service的问题
  14. show master status, show slave status中的Executed_Gtid_Set
  15. Swift 2.x 升为 swift 3后语法不兼容问题适配
  16. Ant scp upload文件至linux server(用java调用Ant api)
  17. Facebook广告API系列 2 - Audience Management
  18. 在Linux下使用sprintf代替atoi实现整型转化为char*
  19. android ListView几个有用的属性
  20. 【HDU】6110 路径交(2017百度之星) 线段树+RMQ-LCA+树链的交

热门文章

  1. JDOM生成XML文档的一般方法
  2. bootstrap表单按回车会自动刷新页面的问题
  3. Flask form
  4. ROS + Caffe 机器人操作系统框架和深度学习框架笔记 (機器人控制與人工智能)
  5. jquery中获取iframe的id的方法:
  6. 一步一步学习IdentityServer3 (5)
  7. day5模块学习--XML模块
  8. javascript 去除最后一个字符自定义的方法
  9. 【BZOJ】4894: 天赋
  10. Codeforces Round #334 (Div. 1) B. Moodular Arithmetic