最长上升奇偶子序列

---

📘 题目描述

给你一个长度为 $n,n\leq 5000$ 的序列，请找到它的一个最长的上升且奇偶交替的子序列。

---

💡 解题思路

🔢 状态定义

• f[i][0]：以第 i 个元素结尾且 $a[i]$ 是偶数的 LIS 的长度
• f[i][1]：以第 i 个元素结尾且 $a[i]$ 是奇数的的 LIS 的方案数

---

🔁 状态转移

遍历每对 j < i，如果 a[j] < a[i]：

• 如果 a[j] 是奇数，且 a[i] 是偶数则：
  👉 更新 f[i][0] = max(f[i][0], f[j][1] + 1)

• 如果 a[j] 是偶数，且 a[i] 是奇数则：
  👉 更新 f[i][1] = max(f[i][1], f[j][0] + 1)

🟡 初始化：

• a[i] 为偶则初始化 f[i][0] = 1，反之初始化 f[i][1] = 1。

✅ 统计答案

\[ ans=\max(f_{1,0},f_{1,1},f_{2,0},f_{2,1},\ldots,f_{n,0},f_{n,1}) \]

⏱️复杂度分析

• 时间复杂度：$O(n^2)$
• 空间复杂度：$O(n)$

✅ 代码实现

#include <bits/stdc++.h>
using namespace std;
constexpr int N = 5e3 + 5;
int f[N][2], n, a[N], ans;
int main()
{
    ios::sync_with_stdio(false), cin.tie(0);
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
        if (a[i] % 2 == 0) f[i][0] = 1;
        else f[i][1] = 1;
        for (int j = 1; j < i; j++)
        {
            if (a[j] < a[i])
            {
                if (a[j] % 2 == 1)
                {
                    if (a[i] % 2 == 0) 
                        f[i][0] = max(f[i][0], f[j][1] + 1);
                }
                else
                {
                    if (a[i] % 2 == 1) 
                        f[i][1] = max(f[i][1], f[j][0] + 1);
                }
            }
        }
        ans = max({ans, f[i][0], f[i][1]});
    }
    cout << ans;
    return 0;
}

小优化

状态一维也可以做，转移时保证 $a_j,a_i$ 奇偶性不同即可。

#include <bits/stdc++.h>
using namespace std;
int n;
int a[5005], f[5005]; // 以 a[i] 结尾的最长子序列
int main()
{
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    int ans = 0;
    for (int i = 1; i <= n; i++)
    {
        f[i] = 1;
        for (int j = 1; j < i; j++)
            if (a[j] % 2 != a[i] % 2 && a[j] < a[i])
                f[i] = max(f[i], f[j] + 1);
        ans = max(ans, f[i]);
    }
    cout << ans;
    return 0;
}