CF1919B 题解

yyrwlj · 2024-01-07 13:03:31 · 题解

题目传送门

题意简述

把一个由 1 和 -1 构成的序列分成若干段，使每段和的绝对值乘上段长的和最小，求出这个最小值。

思路

显然，最好让段内的和等于 0，因为这样就会让这一段的贡献为 0。

要是段内的和等于 0，段内 1 和 -1 的个数就要相同。

也就是一个 1 可以抵消一个 -1，一个 -1 也可以抵消一个 1。

然后我们就可以用栈来解决这个问题。判断当前数是否与栈顶元素相同，相同就弹栈，不相同就把当前数加入栈。

最后的答案就是栈内剩余的数个数，因为剩下的无法互相抵消，每个数单独为一段最优。若不单独为一段，还要乘上一个大于 1 的段长。

Code

#include <iostream>
#include <stack>
using namespace std;
char s[5005];
void work()
{
    int n;
    scanf("%d%s", &n, s + 1);
    stack<char> sta;
    sta.push(s[1]);
    for (int i=2;i<=n;i++)
    {
        if (!sta.empty() && sta.top() != s[i])
            sta.pop();
        else
            sta.push(s[i]);
    }
    printf("%d\n", sta.size());
}
int main()
{
    int T;
    scanf("%d", &T);
    while (T--)
        work();
    return 0;
}