解题思路

本题是在“最长上升子序列（LIS）”基础上的扩展：在所有长度为全局最长的上升子序列中，最大化其中属于集合 $Y$ 的元素个数。 采用经典的 $O(n^2)$ 动态规划 思路，并在状态中同时维护两项：

• len[i]：以第 $i$ 颗宝石结尾的 LIS 的最大长度；
• cnt[i]：在所有达到 len[i] 的方案中，包含稀有宝石（在 $Y$ 中）个数的最大值。

转移（对每个 $i$，枚举所有 $j<i$ 且 $C_j<C_i$）：

• 若 len[j] + 1 > len[i]，则更新 len[i] = len[j] + 1，cnt[i] = cnt[j] + isY(C[i])；
• 若 len[j] + 1 == len[i]，则比较 cnt[j] + isY(C[i])，取更大者更新 cnt[i]；
• 初值：len[i] = 1，cnt[i] = isY(C[i])（仅选自己）。

最终答案：设全局最长长度为 L = max(len[i])，输出所有 len[i] == L 中 cnt[i] 的最大值。

该方法等价于对 LIS 做字典序优先级的二指标优化（先长度最大，再稀有数最大），保证正确性且实现简洁。

复杂度分析

• 时间复杂度：$O(n^2)$，其中 $n \le 2000$，可接受。
• 空间复杂度：$O(n)$。

代码实现

Python

# 题面功能写在外部函数里
def max_match_in_LIS(C, Yset):
    n = len(C)
    len_dp = [1] * n                  # 以 i 结尾的 LIS 最大长度
    cnt_dp = [0] * n                  # 在达到该长度下，稀有宝石的最大计数
    for i in range(n):
        cnt_dp[i] = 1 if C[i] in Yset else 0  # 初值
        for j in range(i):
            if C[j] < C[i]:
                # 以 j 转移到 i
                cand_len = len_dp[j] + 1
                cand_cnt = cnt_dp[j] + (1 if C[i] in Yset else 0)
                if cand_len > len_dp[i]:
                    len_dp[i] = cand_len
                    cnt_dp[i] = cand_cnt
                elif cand_len == len_dp[i] and cand_cnt > cnt_dp[i]:
                    cnt_dp[i] = cand_cnt
    L = max(len_dp)
    ans = 0
    for i in range(n):
        if len_dp[i] == L:
            ans = max(ans, cnt_dp[i])
    return ans

# 主函数：读取输入并输出
def main():
    import sys
    data = sys.stdin.read().strip().split()
    it = iter(data)
    n = int(next(it))
    C = [int(next(it)) for _ in range(n)]
    k = int(next(it))
    Y = {int(next(it)) for _ in range(k)}
    print(max_match_in_LIS(C, Y))

if __name__ == "__main__":
    main()

Java

// 类名必须为 Main（ACM 风格）
import java.util.*;

/**
 * 解法：O(n^2) DP，len[i]记录以i结尾的LIS长度，cnt[i]记录在该长度下包含Y元素的最大数量
 */
public class Main {
    // 题面功能写在外部函数里
    static int solve(int[] C, HashSet<Integer> set) {
        int n = C.length;
        int[] len = new int[n];
        int[] cnt = new int[n];
        for (int i = 0; i < n; i++) {
            len[i] = 1;
            cnt[i] = set.contains(C[i]) ? 1 : 0; // 初值：只选自己
            for (int j = 0; j < i; j++) {
                if (C[j] < C[i]) {
                    int candLen = len[j] + 1;
                    int candCnt = cnt[j] + (set.contains(C[i]) ? 1 : 0);
                    if (candLen > len[i]) {
                        len[i] = candLen;
                        cnt[i] = candCnt;
                    } else if (candLen == len[i] && candCnt > cnt[i]) {
                        cnt[i] = candCnt;
                    }
                }
            }
        }
        int L = 0, ans = 0;
        for (int x : len) L = Math.max(L, x);
        for (int i = 0; i < n; i++) {
            if (len[i] == L) ans = Math.max(ans, cnt[i]);
        }
        return ans;
    }

    // 主函数：读取输入并输出
    public static void main(String[] args) {
        // 数据规模较小，使用 Scanner 足够
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] C = new int[n];
        for (int i = 0; i < n; i++) C[i] = sc.nextInt();
        int k = sc.nextInt();
        HashSet<Integer> set = new HashSet<>();
        for (int i = 0; i < k; i++) set.add(sc.nextInt());
        System.out.println(solve(C, set));
        sc.close();
    }
}

C++

// ACM 风格：主函数输入输出，功能函数外部实现
#include <bits/stdc++.h>
using namespace std;

// 题面功能写在外部函数里
int max_match_in_LIS(const vector<long long>& C, const unordered_set<long long>& Y) {
    int n = (int)C.size();
    vector<int> len(n, 1);  // 以 i 结尾的 LIS 最大长度
    vector<int> cnt(n, 0);  // 在该长度下包含 Y 元素的最大数量
    for (int i = 0; i < n; ++i) {
        cnt[i] = (Y.count(C[i]) ? 1 : 0); // 初值
        for (int j = 0; j < i; ++j) {
            if (C[j] < C[i]) {
                int candLen = len[j] + 1;
                int candCnt = cnt[j] + (Y.count(C[i]) ? 1 : 0);
                if (candLen > len[i]) {
                    len[i] = candLen;
                    cnt[i] = candCnt;
                } else if (candLen == len[i] && candCnt > cnt[i]) {
                    cnt[i] = candCnt;
                }
            }
        }
    }
    int L = 0, ans = 0;
    for (int x : len) L = max(L, x);
    for (int i = 0; i < n; ++i) if (len[i] == L) ans = max(ans, cnt[i]);
    return ans;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n; 
    if (!(cin >> n)) return 0;
    vector<long long> C(n);
    for (int i = 0; i < n; ++i) cin >> C[i];
    int k; cin >> k;
    unordered_set<long long> Y;
    Y.reserve(k * 2 + 1);
    for (int i = 0; i < k; ++i) { long long v; cin >> v; Y.insert(v); }
    cout << max_match_in_LIS(C, Y) << "\n";
    return 0;
}

题目内容

在魔法世界中，探险家发现了一排 $n$ 颗魔法宝石，每颗宝石都有独特的魔力值。一条宝石链是指从这排宝石中选取若干题(可以不选成全选)，保持它们原有的相对顺序排列。如果宝石礴的魔力值从左则右严格递增，则称为一条上升宝石链。所有上升宝石链中，长度最长的称为量长上升宝石链。

魔法学院特别关注某然贴有宝石，定义了一个稀有宝石集合 $Y$ ，一条宝石链与集合 $Y$ 的契合康星指这条宝石链中包含的稀有宝石的数量。

约定一排 $n$ 颗宝石的魔力值序列 $C$ 以及稀有宝石集合 $Y$ ，请计算在所有最长上升宝石链中，与集合 $Y$ 的最大契合度是多少(即最多包含多少颗稀有宝石)，输出这个最大契合度。

输入描述

第一行一个正整数 $n$ ,表示宝石的数量。

第二行是 $n$ 个用空格隔开的正整数$C_1,C_,…,C_n$ ，其中 $C_i$ 表示第 $i$ 颗宝石的魔力值。

第三行是一个正整数 $k$ ,表示稀有宝石集合 $Y$ 的大小。

第四行是 $k$ 个用空格隔开的正整数 $y_1,y_2,...,y_k$ ,表示稀有宝石集合 $Y$ 中的 $k$ 颗宝石的魔为值.

$1 ≤ n,k ≤ 2000,1 ≤ c_i,y_i ≤ 10^9$

输出描述

一个整数，表示最长上升宝石链与稀有宝石集合 $Y$ 的最大契合度。

样例1

输入

5
10 20 30 15 25
3
10 15 30

输出

2