议题 (politics.cpp) - 辩论俱乐部成员数量最大化

议题 (politics.cpp) - 辩论俱乐部成员数量最大化

时间限制：1s 空间限制：512 MB

问题描述

在一个包括你自己（成员 1）有 n 个成员的辩论俱乐部中，有 k 个议题需要按顺序讨论。 在每次讨论中，成员都会表达他们同意或不同意的观点。

我们将 Y 定义为同意的成员数量，N 为不同意的成员数量。

每次讨论后，会员根据以下标准离开俱乐部：

• 如果同意的成员多于不同意的成员 (Y > N)，则所有不同意的成员都会离开俱乐部。
• 如果不同意的成员多于同意的成员 (Y < N)，则所有同意的成员都会离开俱乐部。
• 如果平局 (Y = N)，则所有会员均离开俱乐部。

作为俱乐部主席，您的目标是留在俱乐部并最大程度地使得会议后剩余的会员数量更多。 在会议开始之前，您可以了解每个成员对所有 k 个意见的立场，并且你可以在所有会议开始之前就驱逐任意数量的成员（不包括你自己）。

输入格式

第一行包含两个正整数 n 和 k 分别表示成员数量和讨论数量。

接下来 n 行中，第 i 行包含一个长度为 k 的字符串 ti。 字符串 ti 中的第 j 个字符表示第 i 个成员同意或不同意第 j 个意见（如果他们没有在会议开始之前就离开俱乐部的话），“+”号表示同意，“-”号表示不同意。

输出格式

一行一个整数，表示所有会议结束后，包括你自己在内可以留在俱乐部的最大会员人数。

输入样例 1

2 2
++
+-

输出样例 1

1

输入样例 2

1 3
+-+

输出样例 2

1

输入样例 3

4 1
+
-
-
+

输出样例 3

2

输入样例 4

5 4
++++
+--+
++-+
+-++
++++

输出样例 4

2

输入样例 5

4 2
++
--
--
-+

输出样例 5

1

样例解释

对于样例 1，只有第一位成员可以参加会议，否则在讨论第二个议题后，两位成员都会离开。

对于样例 2，只有一名成员出席会议并坚持到最后。

对于样例 3，俱乐部有 4 名成员，会议期间只会讨论一项议题。 让我们根据会议参与者来分析可能的结果：

• 如果只有第一位成员出席，那么他将是会议结束后剩下的唯一成员。
• 如果第一个成员与第二个或第三个成员一起参加，他们将在议题中打成平局，导致他们都离开。
• 如果第一名成员与第二名和第三名成员一起出席，则第一名成员将成为少数派，并在讨论后离开，这与声明相矛盾。
• 如果第一名和第四名成员出席，他们将在讨论过程中达成一致，并保留到最后。
• 如果第一、第二、第四名成员参加，则讨论时第二名成员将成为少数，最后只剩下第一、第四名成员。 如果第二个成员被第三个成员替换，也会发生同样的情况。
• 如果四位成员都参加，讨论过程中就会出现平局，导致所有人离开。

会议结束后剩余成员最多为 2 人。

对于样例 4，俱乐部现有会员 5 名，会议将讨论 4 项议题。

实现最大成员人数的一种方法是只有第一、第三和第五名成员参加会议。 在这种情况下，他们在前两次讨论中都同意，之后在第三次讨论中第三个成员处于少数。 然后，第一名和第五名成员在最后一次讨论中达成一致，这两名成员留到会议结束。

对于样例 5，俱乐部有 4 名成员，将讨论 2 条议题。

如果前三名成员出席会议，则第一位成员将在第一次讨论中成为少数派，并将离开俱乐部。 之后，第二名和第三名成员均不同意第二个意见，并留至会议结束。 这样，会议结束后就会剩下 2 名成员，但这是一个无效的结果，因为它迫使第一个成员离开。 因此，只能只有第一位成员出席会议，此时，达到 1 名成员的最大人数。

数据范围及约定

对于 100% 的数据，1 ≤ n, k ≤ 100

解题思路

根据题意，我们需要找到一种策略，使得在所有的议题中，同意的成员数量最多，同时不同意的成员数量最少。我们可以使用动态规划来解决这个问题。

定义一个二维数组 dp，其中 dp[i][j] 表示在前 i 个议题中，同意的成员数量不少于 j 的最大留下的成员数量。

对于 dp[i][j]，有两种情况：

1. 如果第 i 个议题中同意的成员数量大于等于 j，那么第 i 个议题中同意的成员都可以留下，即 dp[i][j] = dp[i-1][j] + 1。
2. 如果第 i 个议题中同意的成员数量小于 j，那么第 i 个议题中的不同意的成员都必须离开，即 dp[i][j] = dp[i-1][j-1]。

最终的结果就是 dp[k][n]。

算法步骤

1. 读入成员数量 n 和讨论数量 k。
2. 定义一个二维数组 dp，大小为 (k+1) * (n+1)，并初始化为 0。
3. 读入每个成员的立场，并更新 dp 数组： a. 如果立场为 '+'，则 dp[i][j] = dp[i-1][j] + 1。 b. 如果立场为 '-'，则 dp[i][j] = dp[i-1][j-1]。
4. 输出 dp[k][n] 作为结果。

算法复杂度

时间复杂度：O(nk) 空间复杂度：O(nk)