题目链接

前面全是0的情况特判

#include <bits/stdc++.h>

int dp[10][10];
int digit[10]; int DFS(int pos, int val, int zero, bool limit) {
if (pos == -1) {
return 1;
}
int &now = dp[pos][val];
if (!limit && zero && now != -1) {
return now;
}
int d = limit ? digit[pos] : 9;
int ret = 0;
if (zero == 0) {
for (int i=0; i<=d; ++i) {
ret += DFS (pos - 1, i, i, limit && i == d);
}
} else {
for (int i=0; i<=d; ++i) {
if ((i-val) * (i - val) < 4) {
continue;
}
ret += DFS (pos - 1, i, 1, limit && i == d);
}
}
if (!limit && zero) {
now = ret;
}
return ret;
} int solve(int x) {
int n = 0;
while (x) {
digit[n++] = x % 10;
x /= 10;
}
int ret = 0;
return DFS (n - 1, 0, 0, true);
} int main() {
memset (dp, -1, sizeof (dp));
int a, b;
while (scanf ("%d%d", &a, &b) == 2) {
printf ("%d\n", solve (b) - solve (a - 1));
}
return 0;
}

  

最新文章

  1. 更新过程 renewal process
  2. Java关于IO流的介绍
  3. JAVA基础整理-集合篇(一)
  4. tensorflow 学习笔记
  5. SVM3 Soft Margin SVM
  6. 一起来花5分钟写一个PHP入门Demo
  7. ZOJ 3329 - One Person Game
  8. 对于Linux和windows的个人的看法
  9. C++程序设计实践指导1.14字符串交叉插入改写要求实现
  10. php之 有点复杂的 流程管理
  11. HTML的用法
  12. 芝麻HTTP:如何寻找爬虫入口
  13. Centos-7.4_安装_Redis_4.0.8
  14. 【C++】C++中int与string的相互转换
  15. WPF中TreeView控件的使用案例
  16. python正则下载图片
  17. Android转场动画,Avtivity转场动画;
  18. The APK failed to install. Error:Could not parse error string.
  19. linux配置网路 设定主机名 ssh bash命令 通配符
  20. 【[POI2014]HOT-Hotels】

热门文章

  1. Linux下查看软件的安装路径
  2. util类中非静态方法中注入serivce,在controller层是使用util。
  3. Codeforces Round #262 (Div. 2) 1004
  4. javascript数据结构-队列
  5. 如何用angularjs给从后台传来数据添加链接
  6. C语言中史上最愚蠢的Bug
  7. testng 教程
  8. 红黑树/B+树/AVL树
  9. Dictionary读取键值的快捷方法
  10. 20.SqlServer中if跟循环语句