- #include<bits/stdc++.h>
- using namespace std;
- #define ll long long
- int a[20];
- ll dp[20][20/* 可能需要的状态 1*/][20/* 可能需要的状态 2*/];// 不同题目状态不同
- ll dfs(int pos,int state1/* 可能需要的状态 1*/,int state2/* 可能需要的状态 2*/,bool lead/* 这一位的前面是否为零 */,bool limit/* 这一位是否取值被限制 (也就是上一位没有解除限制)*/)
- // 不是每个题都要处理前导零
- {
- // 递归边界, 最低位是 0, 那么 pos==-1 说明这个数枚举完了
- if(pos==-1)
- return 1;/* 这里返回 1, 表示枚举的这个数是合法的, 那么这里就需要在枚举时必须每一位都要满足题目条件, 也就是说当前枚举到 pos 位, 一定要保证前面已经枚举的数位是合法的. */
- // 第二个就是记忆化 (在此前可能不同题目还能有一些剪枝)
- if(!limit && !lead && dp[pos][state1][state2]!=-1)
- return dp[pos][state1][state2];
- /* 常规写法都是在没有限制的条件记忆化, 这里与下面记录状态对应 */
- int up=limit?a[pos]:9;// 根据 limit 判断枚举的上界 up
- ll ans=0;
- // 开始计数
- for(int i=0;i<=up;i++)// 枚举, 然后把不同情况的个数加到 ans 就可以了
- {
- int new_state1=???;
- int new_state2=???;
- /*
- 计数的时候用 continue 跳过不合法的状态, 不再搜索
- */
- // 合法的状态向下搜索
- ans+=dfs(pos-1,new_state1,new_state2,lead && i==0,limit && i==a[pos]);// 最后两个变量传参都是这样写的
- }
- // 计算完, 记录状态
- if(!limit && !lead)
- dp[pos][state1][state2]=ans;
- /* 这里对应上面的记忆化, 在一定条件下时记录, 保证一致性, 当然如果约束条件不需要考虑 lead, 这里就是 lead 就完全不用考虑了 */
- return ans;
- }
- ll solve(ll x)
- {
- // 可能需要特殊处理 0 或者 - 1
- if(x<=0)
- return ???;
- int pos=0;
- while(x)// 把数位分解
- {
- a[pos++]=x%10;// 编号为 [0,pos), 注意数位边界
- x/=10;
- }
- return dfs(pos-1/* 从最高位开始枚举 */,0/* 可能需要的状态 1*/,0/* 可能需要的状态 2*/,true,true);// 刚开始最高位都是有限制并且有前导零的, 显然比最高位还要高的一位视为 0 嘛
- }
- int main()
- {
- memset(dp,-1,sizeof(dp));
- // 一定要初始化为 - 1
- ll le,ri;
- while(~scanf("%lld%lld",&le,&ri))
- {
- printf("%lld\n",solve(ri)-solve(le-1));
- }
- }
其实另一种计数写法对别的题目有一定的启发性, 需要特别注意的是, 无论哪种写法的 dp 结果中存的数字都是和 le 与 ri 无关的. 所以在数位受限时不能取用计算过的 dp 值, 也不能更新 dp 值, 不受限的情况可以重复利用.
一个更简单的模板, 去掉了很多奇奇怪怪的东西, 比如前导 0, 前导 0 的确应该特殊考虑而不能一概而论.
- int dfs(int i, int s, bool e) {
- if (i==-1) return s==target_s;
- if (!e && ~f[i][s]) return f[i][s];
- int res = 0;
- int u = e?num[i]:9;
- for (int d = first?1:0; d <= u; ++d)
- res += dfs(i-1, new_s(s, d), e&&d==u);
- return e?res:f[i][s]=res;
- }
看起来清爽多了, 其中:
f 为记忆化数组;
i 为当前处理串的第 i 位 (权重表示法, 也即后面剩下 i+1 位待填数);
s 为之前数字的状态 (如果要求后面的数满足什么状态, 也可以再记一个目标状态 t 之类, for 的时候枚举下 t);
e 表示之前的数是否是上界的前缀 (即后面的数能否任意填).
for 循环枚举数字时, 要注意是否能枚举 0, 以及 0 对于状态的影响, 有的题目前导 0 和中间的 0 是等价的, 但有的不是, 对于后者可以在 dfs 时再加一个状态变量 z, 表示前面是否全部是前导 0, 也可以看是否是首位, 然后外面统计时候枚举一下位数.
注意:
不满足区间减法性质的话, 不能用 solve(r)-solve(l-1).
来源: http://www.bubuko.com/infodetail-2971513.html