江苏省建设厅的官方网站,wordpress怎么做目录,免费素材库网站,做网站如何让用户注册这不是一篇介绍数位dpdpdp的文章#xff0c;只是我思考后的一些记录#xff0c;怕以后就忘记了。 由于博主太菜不会组合数学#xff0c;以下数位dpdpdp均采用记忆化搜索的方式。 首先最重要的就是状态设计了#xff0c;正常来说数位dpdpdp的状态设计需要包含数的结构和状态…这不是一篇介绍数位dpdpdp的文章只是我思考后的一些记录怕以后就忘记了。 由于博主太菜不会组合数学以下数位dpdpdp均采用记忆化搜索的方式。 首先最重要的就是状态设计了正常来说数位dpdpdp的状态设计需要包含数的结构和状态。 数位dpdpdp的复杂度可以简单理解为开的数组的大小。 对于数位dpdpdp有两种理解 第一种 dpdpdp的状态只与当前数的位数以及要维护的状态有关。在这种理解方式下dpdpdp状态设计通常为f[pos][state]f[pos][state]f[pos][state]由于状态中并未规定上下界所以对于每次查询操作并不需要将其dpdpdp数组清成−1-1−1这样在应对多组查询的时候可能会快一点。在记忆化的时候需要加上flag1...flag1...flag1...等限制上界的变量是否为111即当前位是否可以选任意数在多组测试情况下这个方法跑的还可以。当然这个只跑的快只能在维护一个数的时候跑的快如果你要维护一对数那么记忆化的时候flag1flag2flag1 \And\And flag2flag1flag2才能记忆化这样的话就会慢很多导致TLETLETLE所以当维护两个数及以上的时候最好不要用这种记忆化方式。 写成的代码大概是这样的
if(f[pos][state]!-1flag) return f[pos][state];
if(flag) f[pos][state]ans;
return ans;第二种 在状态中加入0/10/10/1表示是否达到上界即上文中的flag1,flag2...flag1,flag2...flag1,flag2...这样的话由于每次询问的数都不同所以每次都需要将fff数组置为−1-1−1才能记忆化这样的优点和缺点相比于上面的方式很明显优点就是这个状态设计能记录f[pos][state][0]f[pos][state][0]f[pos][state][0]的信息即如果当前位不能自由选也可以记忆化而上面的只能记录下来f[pos][state][1]f[pos][state][1]f[pos][state][1]的信息只不过我们将最后一维省略了。缺点也比较明显每次都需要初始化fff数组让后重新dpdpdp一次不过也不会太慢。 写成代码大概是这样的
if(f[pos][state][flag]!-1) return f[pos][state][flag];
return f[pos][state]ans;对于前导零 当涉及到对数的结构特点进行维护的时候就有可能需要维护一个前导零了。比如说求[l,r][l,r][l,r]内有多少个数的位数中含kkk个000这个时候如果不维护一个前导零的话会将如001000100010中前面两个000也算入答案这显然是不正确的。
数位dpdpdp很多题目求贡献的话都是按位或者按照数来求的。
做过的例题 2020 ICPC 上海 Sum of Log 数位dp 优化状态 hdu 6899 Xor 数位dp FZU - 2042 The Mad Mathematician 数位dp 算贡献
暂时先更这些后面有更好的理解会补充。
