2022.3.24 开始

2022.3.25日打卡

21302 被3整除的子序列

题目大概: 比较基础的状态机模型

思路: f[i][j]表示以第i位结尾，%3==j的种类数量

时间复杂度: O(3*$n^{2}n^2$)

2022.3.25日中午 由美丽序列得到启发，想了一下，发现我们不用去记住每个状态的结尾，故而可以 O(3*$nn$)解决

21303 删括号

本质思想与最长公共子串相似，为了方便我们进行dp转移，状态方程定义为dp[i][j]

表示s串中前i个字符,可以由p串中的前j个得到，o($n^{3}n^3$),第三维循环从k位转移过来

需要用到一个小结论:合法括号串:1)前缀和处处>=0，并且在此时pre==0

21313 美丽序列

题目大概:多维计数问题

f[i][j][k][sum] 每一维都代表约数条件，并且都代表一个准确的位置，方便我们最后计数

一个非常***的错误 分明括号内应该+，我写成( , )%MOD,竟然还未报错

时间复杂度O($40^2\ast 1600\ast 4040^2*1600*40$)

21314 codeforces

题目大概01背包变种

与01背包不同的地方在于价值是动态变化的，动态变化的价值可以预先处理顺序

预先处理顺序之后，我们可以保证如果第i个物品不被选择，那么前i-1个必然不会被选择，

此时符合01背包枚举顺序

时间复杂度(O($n^{2}n^2$))

额外 Acwing 334 数位计数

关于数位dp的若干思考

如果采用迭代的写法的话

分为三种情况:

例如求abcdefg中第四位数字为k的个数

分为

1. $000abc-1\ast pow10(i)000~abc-1*pow10(i)$

2. $1,k>d\mathrm{恰}\mathrm{好}\mathrm{取}pow10(i)1,k>d\; 恰好取pow10(i)$

   $2,k==d\mathrm{恰}\mathrm{好}\mathrm{取}(000-efg)2,k==d\; 恰好取(000-efg)$

   $3,\mathrm{继}\mathrm{续}\mathrm{迭}\mathrm{代}3,继续迭代$

特判的情况为:如果digit==0,那么第一位必不可能填0，那么我们就要从第二位开始枚举

并且在第一种情况的时候，要减去前导0的情况

采用记忆化搜索的写法的话:

下标记得为n->1,边界为u==0

如果采用迭代的下标值的话，结尾会要特判很多种情况，比较麻烦