数据范围n≤20,因此可以考虑暴力枚举每一个子序列,判断枚举的子序列是否满足条件
我们可以使用DFS枚举,也可以使用二进制枚举,枚举选/不选第i个字符,最终构成最终的字符串即可。
首先,我们遍历所有可能的删除方案。由于不能删除两个连续的字符,我们可以使用位运算来表示删除方案。对于字符串中的每个字符,我们都有两种选择:删除它或保留它。因此,总共有2^n种可能的删除方案,其中n是字符串的长度。
然后,对于每一种删除方案,我们检查删除后的字符串是否是黄金串。我们使用一个标志变量来表示当前的删除方案是否有效。如果删除后的字符串中存在两个连续的字符被删除,我们就将标志变量设置为false。
给定一个由小写字母组成的字符串,如果它包含连续子串 $ exttt{gold}$,我们称它为黄金串。
你可以进行如下操作:选择字符串中的若干字符删除,但不能同时删除相邻的两个字符。也就是说,任意两个被删除的字符在原字符串中的位置不相邻。
请求出有多少种删除方案,使得删除后剩下的字符串成为黄金串。注意,不删除任何字符也算一种方案。
约束条件:
By signing up a CodeFun2000 universal account, you can submit code and join discussions in all online judging services provided by us.