主要思路
还是要勤思考,说不定是能想出来的。
考虑对这个序列做后缀和,女性代表-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;
}
// 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;
}
// 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; }
(高度相似,太菜了