【基础】Even More Odd Photos 显示标签 时间限制：C/C++ 1000MS，其他语言 2000MS 内存限制：C/C++ 128MB，其他语言 256MB 难度：基础 分数：100 OI排行榜得分：14(0.1*分数+2*难度) 出题人： 描述 Farmer John 正再一次尝试给他的 N 头奶牛拍照（2≤N≤1000）。 每头奶牛有一个范围在 1…100 之内的整数的「品种编号」。Farmer John 对他的照片有一个十分古怪的构思：他希望将所有的奶牛分为不相交的若干组（换句话说，将每头奶牛分到恰好一组中）并将这些组排成一行，使得第一组的奶牛的品种编号之和为偶数，第二组的编号之和为奇数，以此类推，奇偶交替。 Farmer John 可以分成的最大组数是多少？ 输入描述 输入的第一行包含 N。下一行包含 N 个空格分隔的整数，为 N 头奶牛的品种编号。 输出描述 输出 Farmer John 的照片中的最大组数。可以证明，至少存在一种符合要求的分组方案。 用例输入 1 7 1 3 5 7 9 11 13 用例输出 1 3 提示 输入

```cpp #include <iostream> #include <vector> using namespace std; // 检查是否可以分成指定数量的组 bool canPartition(const vector<int>& cows, int numGroups) { int n = cows.size(); // dp[i][j][k] 表示前 i 头奶牛，分成 j 组，当前组的和的奇偶性为 k（0 为偶数，1 为奇数）是否可行 vector<vector<vector<bool>>> dp(n + 1, vector<vector<bool>>(numGroups + 1, vector<bool>(2, false))); dp[0][0][0] = true; for (int i = 1; i <= n; ++i) { for (int j = 0; j <= numGroups; ++j) { for (int k = 0; k < 2; ++k) { // 情况 1：不开始新的组，继续当前组 if (j > 0) { dp[i][j][k ^ (cows[i - 1] % 2)] = dp[i][j][k ^ (cows[i - 1] % 2)] || dp[i - 1][j][k]; } // 情况 2：开始新的组 if (j > 0) { dp[i][j][cows[i - 1] % 2] = dp[i][j][cows[i - 1] % 2] || dp[i - 1][j - 1][1 - k]; } } } } // 检查分成 numGroups 组，最后一组的奇偶性是否符合要求 return dp[n][numGroups][(numGroups - 1) % 2]; } int main() { int n; cin >> n; vector<int> cows(n); for (int i = 0; i < n; ++i) { cin >> cows[i]; } // 二分查找最大组数 int left = 1, right = n; int result = 1; while (left <= right) { int mid = left + (right - left) / 2; if (canPartition(cows, mid)) { result = mid; left = mid + 1; } else { right = mid - 1; } } cout << result << endl; return 0; } ``` 代码解释 1. `canPartition` 函数： - 该函数用于检查是否可以将奶牛分成指定数量的组。 - 使用三维动态规划数组 `dp[i][j][k]` 来记录前 `i` 头奶牛，分成 `j` 组，当前组的和的奇偶性为 `k`（0 为偶数，1 为奇数）是否可行。 - 对于每头奶牛，有两种选择：不开始新的组，继续当前组；或者开始新的组。 - 最后检查分成指定数量的组，最后一组的奇偶性是否符合要求。 2. `main` 函数： - 读取输入的奶牛数量和每头奶牛的品种编号。 - 使用二分查找来找到最大的组数。 - 调用 `canPartition` 函数来检查是否可以分成指定数量的组。 - 输出最大的组数。 复杂度分析 - 时间复杂度：$O(n^2)$，其中 $n$ 是奶牛的数量。 - 空间复杂度：$O(n^2)$，主要用于动态规划数组。 [2026-02-03 15:18:32 | AI问答 | 841点数解答]