A22622. 金字塔
填空题
困难
知识点
题目描述
金字塔
题目描述
给定长度为 n 的字符串 s。从 s 中提取子序列，组成 pyramid 字符串的方法有多少种？答案需对 109+7取模后输出。
输入格式
第一行：一个整数 n;
第二行：一个字符串 s。
输出格式
输出组成 pyramid 的方法数（取模 109+7）。
输入样例#1
5
pxxxx输出样例#1
0输入样例#2
10
pyyradmiid输出样例#2
4数据范围：
1≤N≤105，s 仅包含小写英文字母。
参考答案
#include <iostream>
#include <string>
#include <vector>
using namespace std;
const int MOD = 1e9 + 7;
const string TARGET = "pyramid";
int main() {
int n;
string s;
cin >> n >> s;
vector<long long> dp(TARGET.length() + 1, 0);
dp[0] = 1; // 空子序列，作为起点
for (int i = 0; i < n; i++) {
char c = s[i];
// 检查当前字符能匹配TARGET中的哪个位置
for (int j = TARGET.length() - 1; j >= 0; j--) {
if (c == TARGET[j]) {
dp[j + 1] = (dp[j + 1] + dp[j]) % MOD;
}
}
}
cout << dp[TARGET.length()] << endl;
return 0;
}
上一题
下一题