牛客网练习题53-A-超越学姐爱字符串题解

﹏ヽ暗。殇╰゛Y 2022-12-28 07:21 71阅读 0赞

### 文章目录 ###

*  题目描述
 *   *  输入描述
     *  输入
     *  输出
     *  说明
 *  原题（PDF）
 *   *  算法分析
     *  解题标程

--------------------

# 题目描述 #

超越学姐非常喜欢自己的名字，以至于英文字母她只喜欢“c”和“y”。因此超越学姐喜欢只含有“c”和“y”的字符串，且字符串中不能出现两个连续的“c”。请你求出有多少种长度为n的字符串是超越学姐喜欢的字符串。  
答案对1e9+7取模。

## 输入描述 ##

> 输入一个整数n。  
> 1<= n <= 100000

## 输入 ##

## 输出 ##

## 说明 ##

> cyy,cyc,yyy,yyc,ycy

# 原题（PDF） #

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzg0NTk1Ng_size_16_color_FFFFFF_t_70]

## 算法分析 ##

这道题目就是一道简单的**动态规划dp**问题，也可以看作是**简单递推**

首先我们每次都在末尾加上"c"或者"y"两个字符

> 长度1：c,y （2）  
> 长度2：cy,yc,yy (3)  
> 长度3：cyc,cyy,ycy,yyc,yyy (5)  
> 长度4：cycy,cyyc,cyyy,ycyc,ycyy,yycy,yyyc,yyyy (8)

可以发现，结尾为"c"的串再加只能加上"y"，而结尾为"y"的字符再加可以加上"c"或者"y"。  
因此假设求长度为 i 的符合要求的串的个数，那么i中字符的来源则是：

> 结尾为"c"的来源为长度为 (i-1) 的每一个结尾为"y"的串提供。  
> 结尾为"y"的来源为长度为 (i-1) 的每一个串提供。

因此在**dp\[i\]\[0\]中设置长度为 i 的结尾为"c"的串的个数，dp\[i\]\[1\]中设置长度为 i 的结尾为"y"的串的个数。**

> DP公式：  
> dp\[i\]\[0\]=dp\[i-1\]\[1\];  
> dp\[i\]\[1\]=dp\[i-1\]\[0\]+dp\[i-1\]\[1\];

*其实这题仔细思考，可以发现这个规律的总结就是Fibonacci数列。可以直接使用Fibonacci的规律去计算这道题*

## 解题标程 ##

#include <cstdio>
    using namespace std;
    
    long long mod=1e9+7;
    long long n;
    long long dp[100005][2];  //0表示结尾为"c"，1表示结尾为"y"
    
    int main()
    {
        
      scanf("%lld",&n);
    
      dp[1][0]=1,dp[1][1]=1;
      for(int i=2;i<=n;i++){
        
        dp[i][0]=dp[i-1][1]%mod;
        dp[i][1]=dp[i-1][0]%mod+dp[i-1][1]%mod;
      }
    
      printf("%lld",(dp[n][0]+dp[n][1])%mod);
    
      return 0;
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzg0NTk1Ng_size_16_color_FFFFFF_t_70]: /images/20221120/ad5ffc947fdf4de29e013d2bd21dad33.png