躲藏

题目链接

 用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;
}

注意!此信息未认证,请谨慎判断信息的真实性!

全部评论
空

相关内容推荐

头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
2022-12-15 17:07
途虎_JAVA
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
01-07 18:24
点赞 评论 收藏
转发
头像 头像
点赞 评论 收藏
转发
头像 会员标识 头像
点赞 评论 收藏
转发
点赞 收藏 评论
分享

全站热榜

正在热议