一. 题目

二. 思路

三. 代码

const int N=2, M=2e3+10, S=3, MOD=1e9+7, Base=1000;
using LL=long long;

class DP
{
public:
    unordered_map<char, int> st;//状态映射
    int sr[S][S];//分数
    LL f[N][M][S];
public:
    void init(int n, const char s[])
    {
        st['F']=0, st['W']=1, st['E']=2;
        sr[0][0]=0, sr[0][1]=-1, sr[0][2]=1;//F
        sr[1][0]=1, sr[1][1]=0, sr[1][2]=-1;//W
        sr[2][0]=-1, sr[2][1]=1, sr[2][2]=0;//E
        fill(&f[0][0][0], &f[0][0][0]+N*M*S, 0);

        for(int k=0;k<3;++k)
        {
            int grade=sr[k][st[s[0]]];//当B起始位置状态为k时的得分
            f[0][Base+grade][k]=1;
        }
    }

    LL work(int n, const char s[])
    {
        init(n, s);
        for(int i=1;i<n;++i)//从1开始，因为0的所有方案init()时已经计算过
        {
            int id=i+1;//当前是第几个字符
            fill(&f[i&1][0][0], &f[i&1][0][0]+M*S, 0);
            for(int j=-id;j<=id;++j)//当前分差
                for(int k=0;k<3;++k)//当前B状态
                    for(int p=0;p<3;++p)//i-1的B状态
                        if(k!=p)
                        {
                            int grade=sr[k][st[s[i]]];//当前分差得分
                            if(j-grade>=-id+1&&j-grade<=id-1)//i-1时的分差合法值
                                f[i&1][Base+j][k]=(f[i&1][Base+j][k]+f[i-1&1][Base+j-grade][p])%MOD;
                        }
        }
        LL ans=0;
        for(int j=1;j<=n;++j)
            for(int k=0;k<3;++k)
                ans=(ans+f[n-1&1][Base+j][k])%MOD;
        return ans;
    }
}dp;

class Solution {
public:
    int countWinningSequences(string s) {
//        std::string str = "Hello, World!";
//        // 创建一个可修改的 char 数组
//        char charArray[100]; // 确保数组足够大
//        str.copy(charArray, str.size());
//        charArray[str.size()] = '\0'; // 添加结束符
//
//     c_str()是只读的数组
        return dp.work(s.size(), s.c_str());
    }
};