windy数
2020-12-13 05:12
标签：acm dp 题目链接
windy数 标签：acm dp 原文地址：http://blog.csdn.net/wty__/article/details/38023079
windy数：不含前导零且相邻两个数字之差至少为2的正整数。输入x、y，求[x,
y]内的windy数的个数
简单的数位DP，注意前导零的影响int f[20][10], bits[20];
int dfs(int pos, int pre, bool lmt, bool first)
{
if (pos == -1) return 1;
if (!lmt && ~f[pos][pre]) return f[pos][pre];
int u = lmt ? bits[pos] : 9, ret = 0;
for (int i = 0; i = 2))
ret += dfs(pos - 1, i, lmt && i == u, first && !i);
}
return lmt || first ? ret : f[pos][pre] = ret;
}
int calc(int n)
{
CLR(f, -1);
int len = 0;
while (n)
{
bits[len++] = n % 10;
n /= 10;
}
return dfs(len - 1, 0, true, true);
}
int main()
{
//freopen("0.txt", "r", stdin);
int a, b;
while (~RII(a, b))
{
cout
上一篇：Spring框架：
下一篇：【JavaSE】集合（1）