暗黑的字符串---递推公式

我会带着你远行 2022-06-09 09:25 179阅读 0赞

## 题目描述 ##

一个只包含'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

#include<iostream>
    #include<string>
    using namespace std;
    
    int main()
    {
        int n;
        while(cin>>n)
          {
              long long f[31];  //注意结果有可能超出int型范围，需要用long long型
              f[1]=3;
              f[2]=9;
              for(int i=3;i<=n;i++)
                  f[i]=2*f[i-1]+f[i-2];  //递推公式需证明
              cout<<f[n]<<endl;
          }
        return 0;
    }

图片来自：https://www.nowcoder.com/profile/3738522/codeBookDetail?submissionId=12845252

![964976_1473736361531_560EE1C917735D766A0A56AC2EFBB34A][]

[964976_1473736361531_560EE1C917735D766A0A56AC2EFBB34A]: /images/20220609/aed701d4e3bc4aab921f170a94dc1563.png

发表评论取消回复

表情：

评论列表（有 0 条评论，179人围观）

还没有评论，来说两句吧...

相关阅读

相关约瑟夫环——公式法（递推公式）

约瑟夫问题约瑟夫问题是个著名的问题：N个人围成一圈，第一个人从1开始报数，报M的将被杀掉，下一个人接着从1开始报。如此反复，最后剩下一个，求最后的胜利者。例如只有

痛定思痛。/ 2024年04月01日 09:42/ 0 赞/ 58 阅读

相关递推与递归

递推 include <stdio.h> include <stdlib.h> int main(int argc, char argv[])

忘是亡心i/ 2022年12月12日 04:55/ 0 赞/ 222 阅读

相关 [编程题]暗黑的字符串

一个只包含'A'、'B'和'C'的字符串，如果存在某一段长度为3的连续子串中恰好'A'、'B'和'C'各有一个，那么这个字符串就是纯净的，否则这个字符串就是暗黑的。例如：

比眉伴天荒/ 2022年09月30日 13:49/ 0 赞/ 166 阅读

相关 poj3597 Polygon Division +动态规划+递推公式+公式转化技巧

poj3597 Polygon Division +动态规划+递推公式+公式转化技巧题目链接：[http://poj.org/problem?id=3597][http_po

绝地灬酷狼/ 2022年07月16日 07:53/ 0 赞/ 184 阅读

相关递推—构造字符串

Problem Description UMR 闲来无聊玩起了自己的名字，现在的她想知道对于给定的长度 n，只用自己的 ‘U’, ‘M’, ‘R’ 这 3 个字符最多能构成

待我称王封你为后i/ 2022年07月11日 07:20/ 0 赞/ 164 阅读

相关暗黑的字符串---递推公式

题目描述一个只包含'A'、'B'和'C'的字符串，如果存在某一段长度为3的连续子串中恰好'A'、'B'和'C'各有一个，那么这个字符串就是纯净的，否则这个字符串就是暗黑

我会带着你远行/ 2022年06月09日 09:25/ 0 赞/ 180 阅读

相关错排问题的递推公式

问题描述考虑一个n个数字的排列，使所有的数字都不在自己所对应序号的位置上，这样的一个排列就称为原排列的一个错排，现在给定一个数字n，求解所有可能的错排的个数。分析

痛定思痛。/ 2022年05月16日 03:15/ 0 赞/ 229 阅读

相关 [TJOI2019]甲苯先生的字符串——矩阵乘法+递推

题目链接： [\[TJOI2019\]甲苯先生的字符串][TJOI2019] 我们用一个$26\26$的$01$矩阵记录任意两个字符是否能相邻。设$f\[i\

电玩女神/ 2022年01月13日 04:27/ 0 赞/ 253 阅读

相关两道递推公式题的解题报告

T1（阿牛的EOF牛肉串）题意：一串由EOF三个字母组成的长度为\\(n\\)的字母串，不能出现连续的OO，求字符串种类数\\(f\[n\]\\) 答案：\

Bertha 。/ 2021年12月24日 19:19/ 0 赞/ 221 阅读

相关递推（二）：递推法的应用

下面通过一些典型实例及其扩展来讨论递推法的应用。【例2】骨牌铺方格在2×n的一个长方形方格中，用一种2×1的骨牌铺满方格。输入n（n<=40），

青旅半醒/ 2021年11月24日 00:22/ 0 赞/ 365 阅读