成都网站建设推广详情,建设手机网站包括哪些费用吗,和两个黑人同时做网站,开发公司宣传语1026: [SCOI2009]windy数 Description windy定义了一种windy数。不含前导零且相邻两个数字之差至少为2的正整数被称为windy数。 windy想知道#xff0c;在A和B之间#xff0c;包括A和B#xff0c;总共有多少个windy数#xff1f; Input 包含两个整数#xff0c;A B。 Outp… 1026: [SCOI2009]windy数 Description windy定义了一种windy数。不含前导零且相邻两个数字之差至少为2的正整数被称为windy数。 windy想知道在A和B之间包括A和B总共有多少个windy数 Input 包含两个整数A B。 Output 一个整数 Sample Input 【样例一】 1 10 【样例二】 25 50 Sample Output 【样例一】 9 【样例二】 20 HINT 100%的数据满足 1 A B 2000000000 。 数位DP统计类问题。上下界均在int范围内故不必用long long这样的判断是很有必要的。 包括AB。我们通常可以方便算出1~n-1的范围内符合条件的总数。所以只需要1~(A1)-1减去1~B-1即可。 DP方程很好写但统计确实需要分段。本人最开始想少做些事情但JIJI了否则极复杂也算是刷新了对数位DP的理解。 1~910~99100~9991000~9999……先把位数为1至cnt-1计入100..0~(x-1)99..9确定最高位 x00..0~x(y-1)9..9xy0..0~xy(z-1)9..9……高位到低位如果高位已经出现非法直接退出 1 /**************************************************************2 Problem: 10263 User: Doggu4 Language: C5 Result: Accepted6 Time:0 ms7 Memory:820 kb8 ****************************************************************/9
10 #include cstdio
11 const int N 15;
12 int a, b, f[N][10], ans;
13 int abs(int a) {return a0?a:-a;}
14 int DP(int k,int i) {
15 if(f[k][i]) return f[k][i];
16 if(k1) return f[k][i]1;
17 for( int j 0; j 9; j ) if(abs(i-j)2) f[k][i]DP(k-1,j);
18 return f[k][i];
19 }
20 void CAL(int num,int delta) {//cal 0~num-1
21 int digit[N], cnt 0;
22 while(num) digit[cnt]num%10,num/10;
23 for( int bit 1; bit cnt; bit ) //先把长度为1至cnt-1计入
24 for( int i 1; i 10; i )
25 ans delta*DP(bit,i);
26 for( int i 1; i digit[cnt]; i ) //确定最高位
27 ans delta*DP(cnt,i);
28 for( int bit cnt-1; bit 1; bit-- ) {
29 for( int i 0; i digit[bit]; i ) if(bitcnt||abs(i-digit[bit1])2) ans delta*DP(bit,i);
30 if(abs(digit[bit]-digit[bit1])2) break;//如果高位已经出现非法直接退出
31 }
32 }
33 int main() {
34 scanf( %d%d, a, b );
35 CAL(b1,1);
36 CAL(a,-1);
37 printf(%d\n,ans);
38 return 0; 数位DP 转载于:https://www.cnblogs.com/Doggu/p/bzoj1026.html
