Description

现有两个煤矿, 每个煤矿都雇用一组矿工. 采煤工作很辛苦, 所以矿工们需要良好饮食. 每当一辆食品车到达煤矿时, 矿工们便会产出一定数量的煤. 有三种类型的食品车: 肉车, 鱼车和面包车. 矿工们喜欢变化的食谱. 如果提供的食品能够不断变化, 他们的产煤量将会 增加. 每当一个新的食品车到达煤矿时, 矿工们就会比较这种新的食品和前两次 (或者少于 两次, 如果前面运送食品的次数不足两次) 的食品, 并且:

  • 如果这几次食品车都是同一类型的食品, 则矿工们产出一个单位的煤.
  • 如果这几次食品车中有两种不同类型的食品, 则矿工们产出两个单位的煤.
  • 如果这几次食品车中有三种不同类型的食品, 则矿工们产出三个单位的煤.

预先已知食品车的类型及其被配送的顺序. 通过确定哪车食品送到哪个煤矿可以影响产煤量. 食品车不能被拆分, 每个食品车必须被全部送到一个或另一个煤矿. 两个煤矿也并不要求接收相同数量的食品车 (事实上, 也允许将所有食品车都送到一个煤矿). 任务给出食品车的类型及其被配送的顺序, 要求你写一个程序, 确定哪个食品车应被送到煤矿 \(1\), 哪个 食品车应被送到煤矿 \(2\), 以使得两个煤矿的产煤量的总和最大.

Input

输入的第一行包含一个整数 \(n\), 表示食品车的数目. 第二行包含一个由 \(n\) 个字符组成的字符串, 按照配送顺序依次表示食品车配送的食品的类型. 每个字符是以下三个大写字母之一:"M" (表示肉类),"F" (表示鱼类) 或 "B" (表示面包).

Output

输出一个整数, 表示最大的总产煤量.

Sample Input

6
MBMFFB

Sample Output

12

Data Range

对于 45% 的数据, 满足:\(1 \leq n \leq 20\)

对于 100% 的数据, 满足:\(1 \leq n \leq 100000\)

Explanation

难道这真的是 IOI 题目...... (雾)

就是一道看一眼就能口 A 的巨水滚动数组状态转移动规题~

大概分析一下时间复杂度吧, 考虑有 \(m\) 种食物, 矿工会考虑 \(k\) 天的食谱, 则全局的 时间复杂度应该是:

\[O(n \cdot m^{2 k - 2})\]

然后果断发现 \(m = 3, k = 3\) 可以在理论上 \(O(n)\) 水过

Source Code


#include <iostream>
#include <cstdlib>
#include <cstdio>

#define maximize(__x,__y) __x=max(__x,__y)
#define rep(_var,_begin,_end) for(int _var=_begin;_var<=_end;_var++)
using namespace std;
typedef long long lli;
const int maxn = 100100;

int n, arr[maxn];
int dp_arr[2][4][4][4][4];
char str[maxn];

int produce_coal(int a, int b, int c)
{
    // Sorted by time is t_a < t_b < t_c
    int res = 1;
    if (a != 0 && a != b && a != c) res++;
    if (b != 0 && b != c) res++;
    return res;
}

int main(int argc, char** argv)
{
    scanf("%d", &n);
    scanf("%s", str + 1);
    for (int i = 1; i <= n; i++) {
        if (str[i] == 'M') arr[i] = 1;
        else if (str[i] == 'F') arr[i] = 2;
        else if (str[i] == 'B') arr[i] = 3;
    }
    // Dynamic programming with rolling arrays
    int now = 1, last = 0;
    #define dp(_1,_2,_3,_4,_5) dp_arr[_1][_2][_3][_4][_5]
    // Clearing data of last position
    rep(a1, 0, 3) rep(a2, 0, 3) rep(b1, 0, 3) rep(b2, 0, 3)
        dp(last, a1, a2, b1, b2) = -1;
    dp(last, 0, 0, 0, 0) = 0;
    // Main procedure of DP
    for (int i = 1; i <= n; i++) {
        rep(a1, 0, 3) rep(a2, 0, 3) rep(b1, 0, 3) rep(b2, 0, 3) {
            dp(now, a1, a2, b1, b2) = -1;
        }
        rep(a1, 0, 3) rep(a2, 0, 3) rep(b1, 0, 3) rep(b2, 0, 3) {
            // Last position required is invalid
            if (dp(last, a1, a2, b1, b2) < 0)
                continue;
            int cur = arr[i];
            // Evaluating coal production
            int prod_a = produce_coal(a1, a2, cur);
            maximize( dp(now, a2, cur, b1, b2), dp(last, a1, a2, b1, b2) + prod_a );
            int prod_b = produce_coal(b1, b2, cur);
            maximize( dp(now, a1, a2, b2, cur), dp(last, a1, a2, b1, b2) + prod_b );
        }
        swap(now, last);
    }
    // Retrieving result
    int res = 0;
    rep(a1, 0, 3) rep(a2, 0, 3) rep(b1, 0, 3) rep(b2, 0, 3)
        maximize(res, dp(last, a1, a2, b1, b2));
    printf("%d\n", res);
    return 0;
}