小红拿到了一个仅由数字字符组成的字符串。她准备选择一个非空子序列,使得该子序列中不包含连续的"61"子串。 小红想知道,有多少种不同的子序列选择方式?答案对1000000007取模。 输入描述:一个仅由数字组成的字符串,长度不超过100000 输出描述:满足题目条件的子序列的数量 示例1: 输入 12 输出 3 说明:有三个非空子序列,均符合条件 示例2: 输入 654321 输出 62 用c++代码解决该问题并详细解释
时间: 2024-04-07 10:33:43 浏览: 17
为了解决这个问题,可以使用动态规划的方法来计算满足条件的子序列数量。
首先,定义一个二维数组dp,其中dp[i][j]表示以第i个字符结尾、长度为j的子序列中满足条件的数量。
然后,遍历给定的字符串,对于每个字符,计算以该字符结尾的满足条件的子序列数量。
具体的计算方法如下:
1. 如果当前字符不是'6'或'1',则可以将前一个字符结尾的所有满足条件的子序列都加入到以当前字符结尾的子序列中,即dp[i][j] = dp[i-1][j]。
2. 如果当前字符是'6',则不可以将前一个字符结尾的以'1'结尾的子序列加入到以当前字符结尾的子序列中,即dp[i][j] = dp[i-1][j] - dp[i-1][j-1]。
3. 如果当前字符是'1',则可以将前一个字符结尾的所有满足条件的子序列加入到以当前字符结尾的子序列中,同时还可以将前一个字符结尾的以'6'结尾的子序列加入到以当前字符结尾的子序列中,即dp[i][j] = dp[i-1][j] + dp[i-1][j-1]。
最后,将所有以不同字符结尾且长度不同的满足条件的子序列数量累加,即为所求答案。
以下是对应的C++代码实现:
```cpp
#include <iostream>
#include <vector>
using namespace std;
int main() {
string s;
cin >> s;
int n = s.length();
vector<vector<int>> dp(n + 1, vector<int>(n + 1, 0));
for (int i = 1; i <= n; i++) {
dp[i][1] = 2; // 单个字符满足条件的子序列数量为2
for (int j = 2; j <= i; j++) {
dp[i][j] = dp[i-1][j] + dp[i-1][j-1]; // 默认情况下,以当前字符结尾的子序列数量为前一个字符结尾的子序列数量加上以当前字符结尾的子序列数量
if (s[i-1] == '6') {
dp[i][j] -= dp[i-1][j-1]; // 如果当前字符是'6',则需要减去以前一个字符结尾的以'1'结尾的子序列数量
}
}
}
int ans = 0;
for (int i = 1; i <= n; i++) {
ans = (ans + dp[n][i]) % 1000000007;
}
cout << ans << endl;
return 0;
}
```
以上代码通过动态规划的方式计算满足条件的子序列数量,并将最终结果对1000000007取模。
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![txt](https://img-home.csdnimg.cn/images/20210720083642.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![doc](https://img-home.csdnimg.cn/images/20210720083327.png)
![txt](https://img-home.csdnimg.cn/images/20210720083642.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)