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