BZOJ 1026 windy数
发布日期:2021-09-05 00:32:52 浏览次数:15 分类:技术文章

本文共 990 字,大约阅读时间需要 3 分钟。

思路:

数位dp

代码:

#include
using namespace std;#define LL long long #define pb push_back#define mem(a, b) memset(a, b, sizeof(a))int a[15];int dp[15][15];int dfs(int pos, int pre, bool limit, bool zero) { if (pos == -1) return 1; if(!limit && !zero && ~dp[pos][pre]) return dp[pos][pre]; int top = limit ? a[pos] : 9; int ans = 0; for (int i = 0; i <= top; i++) { if(zero){ ans += dfs(pos - 1, i, limit&&i==a[pos], zero&&i==0); } else { if(abs(pre - i) <= 1) continue; ans += dfs(pos - 1, i, limit&&i==a[pos], zero&&i==0); } } if(!limit && !zero) dp[pos][pre] = ans; return ans;}int solve(int n) { int cnt = 0; mem(a, 0); while (n) { a[cnt++] = n % 10; n /= 10; } return dfs(9, 0, 1, 1);} int main() { int a, b; scanf("%d%d", &a, &b); mem(dp, -1); printf("%d\n",solve(b) - solve(a - 1)); return 0;}

 

转载于:https://www.cnblogs.com/widsom/p/8818775.html

转载地址:https://blog.csdn.net/weixin_34228387/article/details/93214547 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!

上一篇:CustomMultipleDropDownBox
下一篇:tornado 初识

发表评论

最新留言

表示我来过!
[***.240.166.169]2024年04月20日 18时43分30秒