简答题
偏难
#13127
金字塔 给定长度为 n 的字符串 s。从 s 中提取子序列,组成 pyramid 字符串的方法有多少种?答案需对 10 9 +7取模后输出。 时间限制:1000…
金字塔
给定长度为 n 的字符串 s。从 s 中提取子序列,组成 pyramid 字符串的方法有多少种?答案需对 109+7取模后输出。
时间限制:1000ms内存限制:256MB
输入格式
第一行:一个整数 n;
第二行:一个字符串 s。
输出格式
输出组成 pyramid 的方法数(取模 109+7)。
输入样例#1
5 pxxxx
输出样例#1
0
输入样例#2
10 pyyradmiid
输出样例#2
4
数据范围:
1≤N≤105,s 仅包含小写英文字母。
答案与解析
正确答案:<pre class="brush:cpp;toolbar:false">#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;
}</pre>
这道题暂未补解析。