摘要
Title: 1884. COW
Tag: dp、记忆化搜索
Memory Limit: 64 MB
Time Limit: 1000 ms

Powered by:NEFU AB-IN

Link

• 题意
• 思路
• 代码

1884. COW

• 题意

  奶牛贝茜在她最喜欢的牧场中发现了一块石碑，上面刻有神秘的碑文。
  碑文的文字似乎来自一种神秘的古代语言，可看作一个只包含 C,O,W 三种字符的字符串。
  尽管贝茜无法解密该文字，但是她很欣赏 C,O,W 按顺序构成她最喜欢的单词 COW。
  她想知道 COW 在碑文中一共出现了多少次。
  她不介意 C,O,W 之间是否存在其他字符，只要这三个字符按正确的顺序出现即可。
  她也不介意多个不同的 COW 是否共享了一些字符。
  例如，COW 在 CWOW 中只出现一次，在 CCOW 中出现两次，在 CCOOWW 中出现八次。
  给定碑文中的文字，请帮助贝茜计算 COW 出现的次数。

• 思路

  如果遍历到‘O’，它只会与前面的‘C’组成”CO“，所以不需要管后面的‘C’的数量
  同理如果遍历到‘W’，它只会与前面的‘CO’组成”COW“，所以不需要管后面的‘CO’的数量
  记录当前‘C’，“CO”，“COW”的个数

• 代码

  '''
  Author: NEFU AB-IN
  Date: 2022-01-22 21:11:33
  FilePath: \ACM\Acwing\1884.py
  LastEditTime: 2022-01-22 21:11:34
  '''
  if __name__ == '__main__':
      n = int(input())
      s = input()
      c, o, w = 0, 0, 0
      for i in s:
          if i == 'C':
              c += 1 #C的数量
          elif i == 'O':
              o += c #CO的数量
          else:
              w += o #COW的数量
      print(w)