Even More Odd Photos：求解 Farmer John 奶牛分组最大组数的算法解析

```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)$，主要用于动态规划数组。 ######[AI问答 | 841点数解答 | 2026-02-03 15:18:32]