首页 > 代码库 > [BZOJ 1026][SCOI2009]windy数（数位Dp）
[BZOJ 1026][SCOI2009]windy数（数位Dp）
Description
windy定义了一种windy数。不含前导零且相邻两个数字之差至少为2的正整数被称为windy数。 windy想知道，
在A和B之间，包括A和B，总共有多少个windy数？
Solution
dp[i][j] i位数中有多少个以j开头的windy数
work(n)是求1~n-1有多少个windy数 n是一个len位数，用bit[i]储存第i位上的数字
可以分为几部分：
1.1~len-1位数中有多少个windy数
2.len位数中最高位与n不同的数
3.len位数中最高位与n相同的数（需要一位一位地推）
#include<iostream>#include<cstdio>#include<cstdlib>#include<cstring>typedef long long LL;using namespace std;LL a,b,dp[15][10],bit[15];void init(){ for(int i=0;i<=9;i++) dp[1][i]=1; for(int i=2;i<=10;i++) for(int j=0;j<=9;j++) for(int k=0;k<=9;k++) if(abs(k-j)>=2) dp[i][j]+=dp[i-1][k];}LL work(LL n){ LL res=0;int len=0; while(n) { bit[++len]=n%10; n/=10; } for(int i=len-1;i>=1;i--) { for(int j=1;j<=9;j++) res+=dp[i][j]; } //part 1 for(int i=1;i<=bit[len]-1;i++) res+=dp[len][i]; //part 2 for(int i=len-1;i>0;i--) { for(int j=0;j<=bit[i]-1;j++) { if(abs(bit[i+1]-j)>=2) res+=dp[i][j]; } if(abs(bit[i]-bit[i+1])<2)break; } //part 3 return res;}int main(){ init(); scanf("%lld%lld",&a,&b); printf("%lld\n",work(b+1)-work(a)); return 0;}
[BZOJ 1026][SCOI2009]windy数（数位Dp）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。