躲藏

题目链接

 用dp[i,j]来表示前i个字符中 匹配的字符j个数 j这个维度是子序列的长度 这题中j的长度就为4 分别为1,2,3,4

• 则状态转移方程为：

dp[i,1] = dp[i - 1][1] + (s[i] == 'c')
dp[i,2] = dp[i - 1][2] + (s[i] == 'w') * dp[i - 1,1]
dp[i,3] = dp[i - 1][3] + (s[i] == 'b') * dp[i - 1,2]
dp[i,4] = dp[i - 1][4] + (s[i] == 'c') * dp[i - 1,3]

代码

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const ll mod = 2000120420010122;
const int maxn = 2e5 + 10;

ll dp[maxn][5];
char s[maxn];

int main()
{
    while(scanf("%s",s + 1) == 1){
        int len = strlen(s + 1);
        for(int i = 1; i <= len; i++){
            s[i] = tolower(s[i]);
            dp[i][1] = (dp[i - 1][1] + (s[i] == 'c')) % mod;
            dp[i][2] = (dp[i - 1][2] + (s[i] == 'w') * dp[i - 1][1]) % mod;
            dp[i][3] = (dp[i - 1][3] + (s[i] == 'b') * dp[i - 1][2]) % mod;
            dp[i][4] = (dp[i - 1][4] + (s[i] == 'c') * dp[i - 1][3]) % mod;
        }
        printf("%lld\n",dp[len][4]);
    }
    return 0;
}

本来这样写就可以过了,但是其实我们还可以再对空间进行优化一下
我们发现,每个状态更新的时候只取决于前一个的状态,所以我们可以去掉第一维只保留第二维
则状态转移方程如下:

       dp[1] = dp[1] + (s[i] == 'c')
        dp[2] = dp[2] + (s[i] == 'w') * dp[1]
        dp[3] = dp[3] + (s[i] == 'b') * dp[2]
        dp[4] = dp[4] + (s[i] == 'c') * dp[3]

代码

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const ll mod = 2000120420010122;
const int maxn = 2e5 + 10;

ll dp[5];

void Solve(char s[])
{
    int len = strlen(s + 1);
    memset(dp, 0, sizeof dp);
    for(int i = 1; i <= len; i++){
        s[i] = tolower(s[i]);
        dp[1] = (dp[1] + (s[i] == 'c')) % mod;
        dp[2] = (dp[2] + (s[i] == 'w') * dp[1]) % mod;
        dp[3] = (dp[3] + (s[i] == 'b') * dp[2]) % mod;
        dp[4] = (dp[4] + (s[i] == 'c') * dp[3]) % mod;
    }
    cout<<dp[4]<<endl;
}

int main()
{
    char s[maxn];
    while(cin>>s + 1){
        Solve(s);
    }
    return 0;
}