2897: 收集魔卡
题目描述
小樱正在辛苦的收集魔卡,我们把每一个地点的魔卡简化到一条直线上,下标从1-n,小樱可以选择从某个地点开始往后连续的搜集(走到某格将代表拾取此处的魔卡),并且在某一地点停止而去战斗(走一格也可以),但是为了在战斗时拥有更多的选择,她想要至少搜集到k个正义的魔卡,同时要避免搜集到召唤恶灵的魔卡,现在小樱想要知道她一共可以有多少个搜集的方案。
输入
第一行输入两个正整数n(1 <= n <= 200000) 和 k(1 <= k <= 15),
第二行输入一行字符串,字符串仅包含大写字母(A到Z)。
E代表正义的魔卡,G代表召唤恶灵的魔卡。
输出
输出小樱的有效搜索的方案数。
样例输入
5 1
EAEGE
样例输出
6
提示
合法的方案:
s[1,1] = E
s[1,2] = EA
s[1,3] = EAE
s[2,3] = AE
s[3,3] = E
s[6,6] = E
int main()
{
int n,k;
cin>>n>>k;
string s;
cin>>s;
int res=0;
for(int i=0;i<n;++i) {
int j=i,sum=0;
while(s[j]!='G'&&s[i]!='G'&&j<n) {
if(s[j]=='E')
++sum;
if(sum>=k)
++res;
++j;
}
}
cout<<res;
return 0;
}