dp专题 公平的坚果和字符串（类似跳台阶dp）

题目链接：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;
}