Description
小伟暑假期间到大草原旅游，在一块石头上发现了一些有趣的碑文。碑文似乎是一个神秘古老的语言，只包括三个大写字母 C、O 和 W。尽管小伟看不懂，但是令他高兴的是，C、O、W的顺序形式构成了一句他最喜欢的奶牛单词“COW”。现在，他想知道有多少次 COW 出现在文本中。 如果 COW 内穿插了其他字符，只要 COW 字符出现在正确的顺序，小伟也不介意。甚至，他也不介意出现不同的 COW 共享一些字母。例如，CWOW 出现了 1 次 COW，CCOW 算出现了2 次 COW，CCOOWW 算出现了 8 次 COW。
Input
第 1 行为 1 个整数 N。 第 2 行为 N 个字符的字符串，每个字符是一个 C、O 或 W。
Output
输出 COW 作为输入字符串的字串出现的次数（不一定是连续的）。 提示：答案会很大，建议用 64 位整数（long long）。
Accepted Code
#include <bits/stdc++.h>
using namespace std;
char ch[100005];
typedef long long LL;
int main()
{
int t = 0;
cin >> t;
memset(ch, 0, sizeof(ch));
scanf("%s", ch);
LL cur_c = 0;
LL cur_co = 0;
LL cur_cow = 0;
for (int i = 0; i < t; i++)
{
if (ch[i] == 'C')
{
cur_c++;
}
else if (ch[i] == 'O')
{
cur_co += cur_c;
}
else if (ch[i] == 'W')
{
cur_cow += cur_co;
}
}
cout << cur_cow << endl;
}
解后反思
本题就比较有趣，利用向后遍历的过程中的状态转移加以优化。
例如在一串字符串中COWCW
第一次读到C cur_c=1 cur_co=0 cur_cow=0
第二次读到O cur_c=1 cur_co+=cur_c=1 cur_cow=0
第二次读到W cur_c=1 cur_co=1 cur_cow+=cur_co=1
以此类推
最终可得所有的COW有2个