时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 32M,其他语言64M 热度指数:13212
本题知识点: 动态规划
算法知识视频讲解

题目描述

一个只包含'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
保存并调试
  • 代码提交记录