欢迎访问 生活随笔！
TAG聚合

生活随笔

当前位置： 首页 > 编程资源 > 编程问答 >内容正文

编程问答

UESTC 250 windy数 数位dp

发布时间：2023/12/18 编程问答 39 豆豆
生活随笔 收集整理的这篇文章主要介绍了 UESTC 250 windy数 数位dp 小编觉得挺不错的,现在分享给大家,帮大家做个参考.

题目链接

1 #include<bits/stdc++.h> 2 using namespace std; 3 #define mem1(a) memset(a, -1, sizeof(a)) 4 #define ll long long 5 int dp[20][20], digit[20], len; 6 ll dfs(int len, int pre, bool fp, bool first) { //first表示前面的数是否全部为0， pre是前一个数 7 if(!len) 8 return 1; 9 if(!first&&!fp && dp[len][pre]!=-1) 10 return dp[len][pre]; 11 int ret = 0, maxx = fp?digit[len]:9; 12 for(int i = 0; i<=maxx; i++) { 13 if(!first) 14 if(abs(i-pre)<2) 15 continue; 16 ret += dfs(len-1, i, fp&&i == maxx, first&&i==0); 17 } 18 if(!fp&&!first) 19 return dp[len][pre] = ret; 20 return ret; 21 } 22 int cal(int n) { 23 len = 0; 24 while(n) { 25 digit[++len] = n%10; 26 n/=10; 27 } 28 return dfs(len, 0, true, true); 29 } 30 int main() 31 { 32 int a, b; 33 mem1(dp); 34 while(~scanf("%d%d", &a, &b)) { 35 printf("%d\n", cal(b)-cal(a-1)); 36 } 37 }

 

转载于:https://www.cnblogs.com/yohaha/p/5035226.html

总结

以上是生活随笔为你收集整理的UESTC 250 windy数 数位dp的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。