2021牛客寒假算法基础集训营1 A. 串(数位dp)

Description

求长度不超过 ，且包含子序列""的、只由小写字母构成的字符串有多少个？

Solution

不妨令 表示枚举到第 个位置的时候状态为

• 其中， 状态是当前是否已满足条件——已出现""的子序列
• 而 状态是当前是否已经出现了字母

发现总共的状态只有 个，记忆化搜索一下即可，每个状态最多只会遍历一次。
ps：我本地 爆栈了，交上去居然过了，非常神奇。
时间复杂度

Code

#include <bits/stdc++.h>
#pragma GCC optimize(3)
#pragma comment(linker, "/STACK:1024000000,1024000000")
typedef long long ll;
using namespace std;

const int N = 1e6 + 5;
const int mod = 1e9 + 7;
const int inf = 0x3f3f3f3f;
ll dp[N][2][2];
ll dfs(int pos, bool state, bool lead) {
  if(pos == -1) {
    return state;
  }
  if(dp[pos][state][lead] != -1) return dp[pos][state][lead];
  ll ans = 0;
  for(int i = 0; i < 26; i++) {
    char now = i + 'a';
    ans += dfs(pos - 1, state || (lead && now == 's'), lead || now == 'u') % mod;
  }
  return dp[pos][state][lead] = ans;
}

void solve() {
  int n; cin >> n;
  memset(dp, -1, sizeof(dp));
  ll ans = 0;
  for (int i = n; i >= 2; i--) {
      ans += dfs(i - 1, 0, 0);
      ans %= mod;
  }
  cout << ans << '\n';
}
int main() {
  ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
  int T = 1; //cin >> T;
  while(T--) {
    solve();
  }
  return 0;
}