字符串中子序列出现个数 dp

Description

很经典的问题 子序列可以是任意的 借用一下某小白赛的题目 在每个字符串中Cwbc作为子序列分别出现了多少次。

Solution

很经典的dp 用dp[i][j]来表示前i个字符中 匹配的字符j个数 j这个维度是子序列的长度 这题中j的长度就为4 分别为1,2,3,4
容易想到转移方程

注意方程中(s[i] =='c')*dp[i-1][j] 等于的话满足条件 才和前面一个状态相乘 因为算的是各种情况组合起来所以是相乘 答案的话很明显是dp[n][4]

正常的话这样就可以过了 但是在这题会卡空间 我们可以看到当前状态只和前一个状态有关 可以直接删除第一维 所以转移方程变为

注意取模操作

Code

#include <bits/stdc++.h>

using namespace std;

#define LL long long

const LL mod = 2000120420010122;

LL dp[5];

int main() {
  ios::sync_with_stdio(0);

  string s;

  while (cin >> s) {
      for(int i = 1;i <= 4;i ++){
          dp[i] = 0;
      }

    for (int i = 0; i < s.size(); 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] % mod << '\n';
  }
  return 0;
}