数位dp

2023-12-12 23:47:34

之前一直没学懂的知识点。可能因为之前的搜索功底太差，导致一直不会记搜实现。补了一些搜索之后补下之前留下的坑。

关于dp

很明显是与数字组成相关的dp。

一般的题型为

求出在给定区间\([l,r]\)中，符合条件\(f(i)\)的数\(i\)的数的个数。

一般转化为\([0,r]\)和\([0,l-1]\)两段来解决，最后将结果相减。

一般是按位dp，数的大小对复杂度影响不大。

所以经常会出现大得离谱的数，遇到时可以考虑数位dp。

从最高位向下搜，到最低位得到方案数，一层一层向上返回答案并累加，最后从最高位得到答案。

基本量：数字位数\(pos\)，答案\(sum\)，最高位限制\(lim\)，前导零\(led\)。

其它变量就题论题，需要啥设啥…（反正设多了不会出错）。

\(1.\)如果当前位\(led=1\)且当前位也是\(0\)，那么当前位也是前导\(0\)。

\(2.\)如果当前位\(led=0\)且当前位不是\(0\)，那么本位作为最高位继续搜。

这一位标记为\(lim\)，这一位能取到的最大值是\(res\)，下一位的标记是\(lim\)&&\((i==res)\)。

当\(lim=1\)和\(led=1\)时不能记录和取用dp值。