首页 > 躲藏
开通博客写题解
头像 小琢卷不动
发表于 2021-11-23 16:10:28
这道题需要格外注意一句话： 不区分大小写。 所以考虑设 dpi,0/1/2/3dp_{i,0/1/2/3}dpi,0/1/2/3​ 表示以 iii 结尾，最后一位恰好匹配到 cwbc 的第 0/1/2/30/1/2/30/1/2/3 个字符的方案数。 然后稍微压一下状态，写出状态转移方程：（代码 展开全文
去ta的博客 赞 (2) 回复(0) 收起
头像 PhantomSamurai
发表于 2020-06-06 17:06:18
Description 很经典的问题 子序列可以是任意的 借用一下某小白赛的题目 在每个字符串中Cwbc作为子序列分别出现了多少次。 Solution 很经典的dp 用dp[i][j]来表示前i个字符中 匹配的字符j个数 j这个维度是子序列的长度 这题中j的长度就为4 分别为1,2,3,4容易想到转 展开全文
去ta的博客 赞 (1) 回复(1) 收起
头像 Enzon
发表于 2023-09-20 15:09:07
长春某理工acm月赛的某题出处，很难评。 正题：我们考虑线性转移，dp[i]表示“Cwbc”中以1~i前字母组成的单词的数量。那么该单词1到i的数量只能由上一个单词1到i-1转移而来，故状态转移为(i=1) dp[i]++, (i>=2)dp[i] += dp[i-1]。由于不区分大小写，故第 展开全文
去ta的博客 赞 (0) 回复(0) 收起
查看本题
查看本题讨论

相关比赛

等你来战

查看全部
牛客竞赛，专业的竞技算法训练平台

扫描二维码，进入QQ群

扫码关注“比赛自动姬”