题解 P6218 【[USACO06NOV] Round Numbers S】
__Watcher
·
·
题解
借此题，总结数位 dp 模板。
在洛谷上打上 数位dp 的标签，这是两道蓝题之一，很适合小结。借助代码来理解吧。下面是所有核心代码。
int dfs(bool limit, bool lead, int pos, int cha) {
if(pos==0) return cha>=30;
if(!limit&&!lead&&vis[pos][cha]) return f[pos][cha];
int res=0;
int up=limit?a[pos]:1;
for(int i=0;i<=up;i++) {
res+=dfs(limit&(i==a[pos]), lead&(i==0), pos-1, cha+(i==0?(lead?0:1):-1));
}
if(!limit&&!lead) vis[pos][cha]=1, f[pos][cha]=res;
return res;
}
变量说明：
$lead$：当前位是否是前导 0；
$pos$：当前是从前向后的第 $pos$ 位。
$cha$：0 比 1 多多少。由于可能出现负数，统统加上了 30；
$vis(pos,cha),f(pos,cha)$：两个记忆化数组，记录没有限制且没有前导 0 时的情况是否搜索过，并记录搜索结果。
---
逐行解释：
`if(pos==0) return cha>=30;`
如果当前所有位搜索完毕，0 比 1 多（差值大于 0）返回 1，否则返回 0。
`if(!limit&&!lead&&vis[pos][cha]) return f[pos][cha];`
如果当前没有特殊限制并且已经搜索过了，直接返回。
`int up=limit?a[pos]:1;`
当前位能去到的最大值。有限制那么就是原数中的 $pos$ 位，没有限制也只能取到 1.
`res+=dfs(limit&(i==a[pos]), lead&(i==0), pos-1, cha+(i==0?(lead?0:1):-1));`
如果之前都有限制且这一位也顶上了位，那么 $limit$ 也是 1；如果之前都是前导 0 且这一位还是 0，那么这一位还是前导 0；位置就往下一位搜；计算新差值（前导 0 统统不算）。
`if(!limit&&!lead) vis[pos][cha]=1, f[pos][cha]=res;`
当前不是特殊情况，那么就记忆下来。
---
小说明：
复杂度如何保证？当 $limit$ 是 1 或者 $lead$ 是 1 的时候并没有记忆化，那么如何保证复杂度？为了让 $limit$ 是 1，每一位都得顶位，只有 $len$ 种情况；如果让 $lead$ 是 1，那么每一位都得是 1，也只有 $len$ 种情况。因此，只有极少数情况未被记忆化，复杂度保障在 $len^2$ 的水平。
---
提供代码，仅供参考：
```cpp
#include<bits/stdc++.h>
using namespace std;
#define ll long long
int read() {
int x=0, f=1; char ch=' ';
while(!isdigit(ch)) {ch=getchar(); if(ch=='-') f=-1;}
while(isdigit(ch)) x=(x<<3)+(x<<1)+(ch^48), ch=getchar();
return x*f;
}
int a[50], len, f[50][65], vis[50][65];
int dfs(bool limit, bool lead, int pos, int cha) {
if(pos==0) return cha>=30;
if(!limit&&!lead&&vis[pos][cha]) return f[pos][cha];
int res=0;
int up=limit?a[pos]:1;
for(int i=0;i<=up;i++) {
res+=dfs(limit&(i==a[pos]), lead&(i==0), pos-1, cha+(i==0?(lead?0:1):-1));
}
if(!limit&&!lead) vis[pos][cha]=1, f[pos][cha]=res;
return res;
}
int solve(int x) {
len=0;
while(x) {
a[++len]=x%2;
x/=2;
}
return dfs(1, 1, len, 30);
}
int main() {
int l=read(), r=read();
cout<<solve(r)-solve(l-1);
}
```