Description

  windy定义了一种windy数。不含前导零且相邻两个数字之差至少为2的正整数被称为windy数。 windy想知道,在A和B之间,包括A和B,总共有多少个windy数?

  一直还是有点怕数位DP的...包括今天做这道简单的小题也花了很久的时间处理细节。

  首先大体的思路非常明显,定义一个DP f[i,j]表示第i位放数字j有多少种方法,可以通过前一位的一些满足的数字推出这一位。

  但是如何来解决在某个数A的范围内呢...?

  并且一旦前面的没有取满,这一位都是可以0..9任意取的

  并且还要考虑以这一位为开头的情况

  没有前导零,也就是说当这一位为0的时候是不能作为开头的。

  思考了一会儿,想出了一种方案。f[i,j]表示第i为放数字j并且从1~i并排除取到原数的方案数

  那么通过f[i-1]然后枚举0~9就可以先得出初步的f[i](因为i-1位以前都没有取到满了,这一位随便怎么取都不会超过原数

  第二部分就是当前数为起点,那么我们枚举1~9,inc(f[i][j])就可以了

  还有一种情况,就是i-1位已经取满了,当前这位只能取0~num[i]这些数(num[i]表示原数在第i位的数字)

  但是我们只能枚举到num[i]-1,因为要维护f[i]这个数组的性质:没有取到满

  注意细节:第三种情况能够转移当且仅当1~i-1位都满足windy数的性质 (这里我们可以用一个bool类型标记)

  处理完之后再判断1~i是否满足windy数的性质

  f[最后一位][0..9]就是答案。

  其实还没有结束...别忘了原数,如果那个bool类型到最后还是为真,说明原数也是一个windy数

  但是显然我们在f数组里是不会统计到原数的,这个时候还要答案+1

  最后还有一个细节,就是特判0的情况,虽然题目保证>=1但是我们要的答案是solve(r)-solve(l-1),还是会即算到0的情况

  要特判solve(0)=0

  前几天写惯了树剖今天几道小题真是爽啊...

  

 /**************************************************************
Problem: 1026
User: mjy0724
Language: Pascal
Result: Accepted
Time:0 ms
Memory:228 kb
****************************************************************/ program bzoj1026;
var i,l,r:longint;
w,num:array[-..]of longint;
f:array[-..,..]of longint; function solve(p:longint):longint;
var i,j,k,ans:longint;
flag:boolean;
begin
if p= then exit();
fillchar(f,sizeof(f),);
for i:= downto do if p div w[i]> then break;
if p div w[i]> then inc(i);
for j:=i downto do num[j]:=p div w[j-] mod ;
for j:= to num[i]- do f[i,j]:=;
flag:=true;
for i:=i- downto do
begin
for j:= to do
for k:= to do if abs(j-k)>= then inc(f[i,j],f[i+,k]);
for j:= to do inc(f[i,j]);
if flag then for j:= to num[i]- do if abs(j-num[i+])>= then inc(f[i,j]);
if abs(num[i]-num[i+])< then flag:=false;
end;
ans:=;
for i:= to do inc(ans,f[,i]);
if flag then inc(ans);
exit(ans);
end; begin
w[]:=;
for i:= to do w[i]:=w[i-]*;
readln(l,r);
writeln(solve(r)-solve(l-));
end.

  

最新文章

  1. 机器学习笔记----Fuzzy c-means(FCM)模糊聚类详解及matlab实现
  2. C语言基础(11)-随机数发生器
  3. DOM 节点操作
  4. MVC5-11 浅谈拦截器
  5. C++Primer 第三章
  6. 个人对js闭包的理解
  7. [转]使用maven镜像
  8. 正整数N是否是素数
  9. DBCP数据源
  10. LSJ_NHibernate第一章 NHibernate介绍
  11. I/O事件
  12. Linux内核中的list用法和实现分析
  13. 初识git--基础命令
  14. poj1011 && uva307 DFS + 剪枝
  15. 基于表单数据的封装,泛型,反射以及使用BeanUtils进行处理
  16. vue项目实现记住密码功能
  17. SOAPwebservice 与Restfull webservice之间的区别
  18. 摘录&lt;小王子&gt;——[法]安东&#183;圣埃克苏佩里
  19. STM32F4 External event -- WFE 待机模式
  20. 在Linux防火墙上过滤外来的ICMP timestamp

热门文章

  1. 对工具的反思 &amp; deadlines与致歉
  2. Android adb shell启动应用程序的方法
  3. 13.0 Excel表格写入
  4. hyperledger composer
  5. npm安装不成功的原因
  6. UVA 11884 A Shooting Game(记忆化搜索)
  7. int,long,long long类型的范围
  8. ng2 搭建本地开发环境
  9. el-table中操作一栏怎么根据当前行的信息显示编辑、删除、编辑完成按钮
  10. JSP表单提交出现中文乱码的解决方法