P3615:如厕计划题解

主要思路

还是要勤思考,说不定是能想出来的。

考虑对这个序列做后缀和,女性代表-1,男性代表+1,然后发现只要保证后缀和一直大于\(-2\)即可。那么,我们可以维护每一段的后缀和,然后维护最大后缀和。

计算答案的时候需要知道要抬升多少才能让整个折线不会碰到\(-2\)的线,找到最大抬升的值就行了(这样都能合法)。

代码

// P3615.cpp
#include <bits/stdc++.h>
#define ll long long

using namespace std;

const int MAX_N = 200100;

ll n, m, ki[MAX_N], prefix[MAX_N], mx_prefix[MAX_N], acc, ans;
char str[MAX_N];

int main()
{
    scanf("%lld%lld", &n, &m);
    for (int i = 1; i <= m; i++)
    {
        scanf("%s%lld", str + 1, &ki[i]);
        int len = strlen(str + 1);
        for (int j = len; j >= 1; j--)
            prefix[i] += (str[j] == 'F' ? -1 : 1), mx_prefix[i] = max(mx_prefix[i], prefix[i]);
        acc += prefix[i] * ki[i];
    }
    if (acc > 0)
        printf("-1"), exit(0);
    ans = 1, acc = 0;
    for (int i = m; i >= 1; i--)
    {
        if (prefix[i] > 0)
            ans = max(ans, acc + (ki[i] - 1) * prefix[i] + mx_prefix[i]);
        else
            ans = max(ans, acc + mx_prefix[i]);
        acc += prefix[i] * ki[i];
    }
    printf("%lld", ans - 1);
    return 0;
}

(高度相似,太菜了


发表评论

邮箱地址不会被公开。 必填项已用*标注