题目链接:http://codeforces.com/contest/1084/problem/C
对于一个由小写拉丁字母组成的字符串s,坚果想找到严格增加的序列p1,p2,…,pk的数量,保证:
对于每个i(1≤i≤k),spi =‘a’。
对于每个i(1≤i<k),存在pi <j <pi + 1且sj ='b’的j。
就是求严格增加的(下标序列)的个数,下标的字符全部是’a’,并且相邻的下标之间存在有下标的字符为’b’。单独的一个下标为’a’的也算一个。
思路:这个跟跳台阶dp类似:如果新增加一个’a’,
➀:如果与上一个'a'之间有'b',那么之前形成的所有序列都可以加上这个a形成新序列,这个'a'的贡献为dp[i]=s+1(自己单独也是一个)
➁:如果与上一个'a'之间没有'b',这个'a'都可以替代上一个'a'。这个'a'的贡献为dp[i]=dp[i-1]
➀高度平行的台阶
➁更高的台阶
每次的可以跳台阶数不定[0, n]。任意台阶可以为起点。
全部的dp数组和为所有的个数。
#include<bits/stdc++.h>
using namespace std;
#define LL long long
const int mod=1000000007;
char a[100005];
LL d[100005]={1};
int p=1;
int main()
{
fgets(a, 100005, stdin);
int n=strlen(a), k=0;
LL s=0;
for(int i=0;i<n;i++)
{
if(a[i]=='a')
{
if(k==0)//如果与上一个'a'之间没有'b'
{
d[p]=(d[p-1])%mod;
s=(s+d[p])%mod;
p++;
}
else//如果与上一个'a'之间有'b'
{
d[p]=(s+1)%mod;
s=(s+d[p])%mod;
p++;
}
k=0;
}
else if(a[i]=='b')
{
if(p!=1)
k=1;
}
}
printf("%lld\n",s);
return 0;
}