首页 > 代码库 > BZOJ 1026 windy数
BZOJ 1026 windy数
Description
windy定义了一种windy数。不含前导零且相邻两个数字之差至少为2的正整数被称为windy数。 windy想知道，在A和B之间，包括A和B，总共有多少个windy数？
Input
包含两个整数，A B。
Output
一个整数。
Sample Input
【输入样例一】
1 10
【输入样例二】
25 50
1 10
【输入样例二】
25 50
Sample Output
【输出样例一】
9
【输出样例二】
20
9
【输出样例二】
20
HINT
【数据规模和约定】
100%的数据，满足 1 <= A <= B <= 2000000000 。
数位dp裸题：f[i][j][k]表示考虑至第i位，填j,且属于k状态的方案数。k = 0为危险状态，k = 1为安全状态。
设A的位数为p1，B的为p2。先dp位数为p1的满足条件数有几个，再dp位数<p1且满足条件的数有几个(全是安全态)。两者相加即为<=A的满足条件的数有几个了。
ans = ans(B) - ans(A-1);
具体见代码(可能略丑，仅供参考):
1 #include<iostream> 2 #include<cstring> 3 #include<cstdio> 4 #include<cmath> 5 #include<cstdlib> 6 using namespace std; 7 8 #define maxn 15 9 int A,B,sum,f[maxn][10][2];10 int num[maxn];11 12 inline int len(int lim)13 {14 int ret = 0,pos = 0,t = lim;15 while (lim) { ++ret; lim/=10; }16 memset(num,0,sizeof(num));17 while (t) { ++pos; num[ret - pos + 1] = t%10; t /= 10; }18 return ret;19 }20 21 inline int dp(int lim)22 {23 if (lim == 0) return 0;24 int ret = 0,n = len(lim),i,j,k;25 memset(f,0,sizeof(f));26 for (i = 1;i < num[1];++i) f[1][i][1] = 1;27 f[1][num[1]][0] = 1;28 for (i = 1;i < n;++i)29 for (j = 0;j < 10;++j)30 {31 if (f[i][j][1])32 for (k = 0;k < 10;++k)33 {34 if (abs(k-j) < 2) continue;35 f[i+1][k][1] += f[i][j][1];36 }37 if (!f[i][j][0]) continue;38 for (k = 0;k <= num[i+1];++k)39 {40 if (abs(k-j) < 2) continue;41 if (k == num[i+1])42 f[i+1][k][0] += f[i][j][0];43 else f[i+1][k][1] += f[i][j][0];44 }45 }46 for (i = 0;i < 10;++i) for (j = 0;j < 2;++j) ret += f[n][i][j];47 memset(f,0,sizeof(f));48 for (i = 1;i < 10;++i) f[1][i][1] = 1;49 for (i = 1;i < n-1;++i)50 for (j = 0;j < 10;++j)51 {52 if (!f[i][j][1]) continue;53 for (k = 0;k < 10;++k)54 {55 if (abs(j - k) < 2) continue;56 f[i+1][k][1] += f[i][j][1];57 }58 }59 for (i = 1;i < n;++i) for (j = 0;j < 10;++j) ret += f[i][j][1];60 return ret;61 }62 63 int main()64 {65 freopen("1026.in","r",stdin);66 freopen("1026.out","w",stdout);67 scanf("%d %d",&A,&B);68 sum = dp(B);69 sum -= dp(A-1);70 printf("%d",sum);71 fclose(stdin); fclose(stdout);72 return 0;73 }
BZOJ 1026 windy数
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。