``Acwing 1884. COW

题目描述

输出给定字符串中COW 作为子序列（不一定连续）的出现次数。
例如，COW
在 CWOW 中只出现一次，
在 CCOW 中出现两次，
在 CCOOWW 中出现八次。

相关概念

简单DP

以背包问题为例
f[i, j]表示考虑前i个物品体积不超过j的最大价值

for(int i = 1; i <= n; i ++)
    for(int j = 0; j <= m; j ++)
    {
        f[i][j] = f[i - 1][j];
        if(j >= v[i]) f[i][j] = max(f[i][j], f[i - 1][j - v[i]] + w[i]);
    }
    cout << f[n][m] << endl;

状态机类型DP

第二维不好确定，故抽象为状态机

故抽象成二维
f[i, j]表示走完第i个字母时变为状态j的方案数

DP分析

s[i]表示字符串中第i个字母

当s[i]为C时，
f[i, 0] = f[i - 1, 0] + 1;
f[i, 1] = f[i - 1, 1];
f[i, 2] = f[i - 1, 2];

当s[i]为O时，
f[i, 0] = f[i - 1, 0];
f[i, 1] = f[i - 1, 1] + 1;
f[i, 2] = f[i - 1, 2];

当s[i]为W时，
f[i, 0] = f[i - 1, 0];
f[i, 1] = f[i - 1, 1];
f[i, 2] = f[i - 1, 2] + 1;

细节

注意可能会爆int

代码

没有用滚动数组

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

typedef long long LL;

const int N = 100010;

int n;
string str;
LL f[N][3];

int main()
{
    cin >> n;
    cin >> str;

    if(str[0] == 'C') f[0][0] ++;

    for(int i = 1; i < n; i ++)
    {
        if(str[i] == 'C')
        {
            f[i][0] = f[i - 1][0] + 1;
            f[i][1] = f[i - 1][1];
            f[i][2] = f[i - 1][2];
        }

        if(str[i] == 'O')
        {
            f[i][0] = f[i - 1][0];
            f[i][1] = f[i - 1][1] + f[i - 1][0];
            f[i][2] = f[i - 1][2];
        }

        if(str[i] == 'W')
        {
            f[i][0] = f[i - 1][0];
            f[i][1] = f[i - 1][1];
            f[i][2] = f[i - 1][2] + f[i - 1][1];
        }
    }

    cout << f[n - 1][2] << endl;

    return 0;
}

使用滚动数组优化

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

typedef long long LL;

const int N = 100010;

int n;
string str;
LL f[N][3];

int main()
{
    cin >> n;
    cin >> str;

    LL a = 0, b = 0, c = 0;

    for(int i = 0; i < n; i ++)
    {
        if(str[i] == 'C') a ++;
        else if(str[i] == 'O') b += a;
        else c += b;
    }

    cout << c << endl;
    return 0;
}