首页 > 试题广场 >

暗黑的字符串

[编程题]暗黑的字符串
  • 热度指数：14081 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 32M，其他语言64M
  • 算法知识视频讲解
一个只包含'A'、'B'和'C'的字符串，如果存在某一段长度为3的连续子串中恰好'A'、'B'和'C'各有一个，那么这个字符串就是纯净的，否则这个字符串就是暗黑的。例如：
BAACAACCBAAA 连续子串"CBA"中包含了'A','B','C'各一个，所以是纯净的字符串
AABBCCAABB 不存在一个长度为3的连续子串包含'A','B','C',所以是暗黑的字符串
你的任务就是计算出长度为n的字符串(只包含'A'、'B'和'C')，有多少个是暗黑的字符串。

输入描述:
输入一个整数n，表示字符串长度(1 ≤ n ≤ 30)


输出描述:
输出一个整数表示有多少个暗黑字符串
示例1

输入

2 3

输出

9 21
算法知识视频讲解
开通博客
头像 重生之我要当分子
发表于 2025-01-07 23:04:42
解题思路 使用动态规划解决： 状态表示： 表示长度为 时，最后三个字符状态为 的字符串数量 状态转移：根据新添加的字符更新状态 注意：只有不包含ABC的字符串才是暗黑的 关键点 状态编码 状态转移 处理边界情况 代码 cpp java python #include & 展开全文
去ta的博客 赞 (0) 回复(0) 收起

问题信息

动态规划
来自：网易2017秋招编程题集合
难度：
87条回答 21930浏览

热门推荐

通过挑战的用户

查看代码

相关试题

暗黑的字符串

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号