一、举例
#1033 :交错和
时间限制：10000ms
单点时限：1000ms
内存限制：256MB
说明
给出数x，从其10个进展的高位到低位依次为a0，a1，an - 1，定义交错和函数：
f(x )=A0-A1A2-.(-1 ) n - 1an - 1
例如：
f ) 3214567(3-21-45-67=4
给出l，r，k，在[l，r]区间中，求出所有F(X )=k的x之和，即：
1405402477702.png
输入
输入数据每行包含三个整数： l、r、k (0lr1018，|k| 100 )。
输出功率
每行输出一个整数来表示结果，考虑到答案可能很大，输出结果类型109 7。
提示
对于示例，满足条件的数量为110和121，因此结果为231=110 121。
1 /*
***********************交错和* * * * * * * * * * * * * * * * * * * * * * * * * * *。
5
6
7 #include
8 #include
9长龙mod=1000000007； 10长龙base [ 20 ]； 11 long long l，r，k，bit[20]，bt，yy； 12结构节点{ 13 long long s，n； //s表示数字，n表示数字个数
14 }； 15节点DP [ 20 ] [ 400 ]； //状态转移
16节点DFS (长pos、长目标、长long limit )//数字dp几乎可以说是模板
17 { 18节点t； 19 t.s=t.n=0； 处理到20if(pos==0)//最后一位，直接判断后返回
21if(target==100 ) 22 t.n=1； 23返回； 24 ) 25if () limit==0) ) dp[pos][target].n！=-1 ) ) returndp[pos][target]； 26长龙tail=limit？ bit[pos] : 9； 27长时间Sgn=(YY-pos ) % 2)？ (-1 ) 3360 ) 1； 确定//符号
28龙龙光头； 29if(pos==YY ) head=1； 30 else head=0； //决定检索的起点和终点
31 for (长龙I=head； i=tail； I ) 32 { 33节点tmp=DFS (pos-1，target - i*sgn，(limit==1) ) i==bit[pos] )； 4if () tmp.n )0) {35 t.n =tmp.n； 36长龙问； 37q=() (tmp.n%mod ) *base[pos] ) mod ) ) I ) % mod； //结果的同余处理
38t.s=(tmp.s ) %mod； 39 t.s %=mod； 40 t.s =q； 41 t.s %=mod； //所有步骤都是一样的
42 ) 44if(limit==0) dp[pos][target]=t； 45返回； 46 ) 47长龙Cal (长龙x，长龙) 48 ) 49长龙Ans=0； 50if(x==-1 )返回0； 51if(x==0)返回0； 52 bt=0； 53while(x ) 54 {55 bt； 56位[ Bt ]=x % 10； 57 x /=10； 59for ) YY=1； yy=bt； yy ) {60memset(DP，-1，sizeofdp )； 61ans=DFS(YY，y 100，yy==bt ).s； //按长度yy的数字进行处理
62ans=(ansmod ) %mod； 63 ) 64返回Ans； 65 ) 66intmain(67 ) 68base[1]=1； 69for(intI=2； i=19； I ) 70base[I]=(base[I-1]*10 ) %mod； 71扫描(' % lld % lld % lld )、l、r、k )； 72//scanf_s('%lld%lld%lld '，l，r，k )；
73 {74 printf('%lld '，(cal(r，k )-cal ) L-1，k ) mod ) %mod )； 75 ) 76返回0； 77 }
视图代码
二、思路分析
给出值的范围，求出区间内的数的交错和给定的数，需要使用数位的dp、记忆搜索及同余定理。
1 .将同一交错和的个数、同一交错和的数字和分别进行dp化检索并书写。
2 .一位数字和两位数字的计算方法不同，分数字位数进行讨论。
3 .由于结果可能较大，所有步骤都需要使用同余定理。
三.数字dp模板
1 const intMAX_DIGITS，MAX_STATUS； 2 LL f[MAX_DIGITS][MAX_STATUS]，bits[MAX_DIGITS]； 3
4LLDFS(intposition，int status，bool limit，boolfirst )5(6if ) position==-1 )7 return s==target_status； 8 if (！ 极限！ first至f [ position ] [ status ] )9 returnf[position][status]； 10 int u=limit？ bits[position] : MAX_BITS； 11 LL ret=0； 12for(intI=0； i=u； I ) 13 { 14 } ret=DFS (位置- 1，next_status ) status，I )，limit i==u，first！ I； 15 ) 16返回限制||| first？ ret : f[pos][status]=ret； (十八)十八
19llcalc(lln ) 20(21clr ) f，-1； 22 int len=0； 23while(n ) 24 ) 25bits[Len]=n； 26 n /=10； 27 ) 28返回DFS (len-1，0，true，true )； ) 30
31intmain(32 ) 33//Freopen(0.txt )、(r )、stdin )；
34 LL a，B； 5while(CINab ) 36 cout calc(b ) b )-calc (a-1 ) ) ) ) ) ) ) )
四.记忆化检索
记忆化检索=以检索形式动态规划的思想
参考文献
1 .算法集的《浅谈数位类统计问题》 ——wzdwt
2 .推酷《数位dp模板》