思路

先假设所有物品都没有贴到“匹配标签”，此时总和为 $\displaystyle \text{base}=\sum_{i=1}^{n} c_i$。

若把某个物品 $i$ 贴上它匹配的 $a_i$ 号标签，总和会增加 $\displaystyle \Delta_i = b_i - c_i$。

由于每种标签只有 $1$ 张，对于同一标签种类 $t$，最多只能选择 一个满足 $a_i=t$ 的物品来获得这次“增量”。为了使总和最大，我们对每个标签种类 $t\in[1,m]$，只需挑选该类下的最大增量

若该最大值为负则不选。

于是答案为

C++

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m;
    if (!(cin >> n >> m)) return 0;

    vector<int> a(n);
    for (int i = 0; i < n; ++i) cin >> a[i];

    vector<long long> b(n), c(n);
    for (int i = 0; i < n; ++i) cin >> b[i];
    for (int i = 0; i < n; ++i) cin >> c[i];

    // base：所有物品都不贴匹配标签时的总和
    long long base = 0;
    for (int i = 0; i < n; ++i) base += c[i];

    // best[t]：标签种类 t 的最大增量 Δ = b[i] - c[i]
    // 初始化为极小值，表示还未出现该标签
    vector<long long> best(m + 1, LLONG_MIN);

    for (int i = 0; i < n; ++i) {
        int t = a[i];                 // 物品 i 匹配的标签种类
        long long delta = b[i] - c[i];// 贴上匹配标签带来的增量
        best[t] = max(best[t], delta);
    }

    long long ans = base;
    // 逐类加入最大非负增量
    for (int t = 1; t <= m; ++t) {
        if (best[t] > 0) ans += best[t];
    }

    cout << ans << "\n";
    return 0;
}

Python

import sys

def main():
    data = list(map(int, sys.stdin.buffer.read().split()))
    it = iter(data)
    n = next(it); m = next(it)

    a = [next(it) for _ in range(n)]
    b = [next(it) for _ in range(n)]
    c = [next(it) for _ in range(n)]

    # base：所有物品都不贴匹配标签时的总和
    base = sum(c)

    # best[t]：标签种类 t 的最大增量 Δ = b[i] - c[i]
    # 初值为 None 表示该标签尚未出现
    best = [None] * (m + 1)
    for i in range(n):
        t = a[i]
        delta = b[i] - c[i]
        if best[t] is None or delta > best[t]:
            best[t] = delta

    ans = base
    # 逐类加入最大非负增量
    for t in range(1, m + 1):
        if best[t] is not None and best[t] > 0:
            ans += best[t]

    print(ans)

if __name__ == "__main__":
    main()

Java

import java.io.*;
import java.util.*;

public class Main {
    // 简单高效的输入读取
    static class FastScanner {
        private final InputStream in;
        private final byte[] buffer = new byte[1 << 16];
        private int ptr = 0, len = 0;
        FastScanner(InputStream is) { in = is; }
        private int read() throws IOException {
            if (ptr >= len) {
                len = in.read(buffer);
                ptr = 0;
                if (len <= 0) return -1;
            }
            return buffer[ptr++];
        }
        int nextInt() throws IOException {
            int c, sgn = 1, x = 0;
            do c = read(); while (c <= ' '); // 跳过空白
            if (c == '-') { sgn = -1; c = read(); }
            while (c > ' ') {
                x = x * 10 + (c - '0');
                c = read();
            }
            return x * sgn;
        }
    }

    public static void main(String[] args) throws Exception {
        FastScanner fs = new FastScanner(System.in);
        int n = fs.nextInt(), m = fs.nextInt();

        int[] a = new int[n];
        for (int i = 0; i < n; i++) a[i] = fs.nextInt();

        long[] b = new long[n];
        long[] c = new long[n];
        for (int i = 0; i < n; i++) b[i] = fs.nextInt();
        for (int i = 0; i < n; i++) c[i] = fs.nextInt();

        // base：所有物品都不贴匹配标签时的总和
        long base = 0;
        for (int i = 0; i < n; i++) base += c[i];

        // best[t]：标签种类 t 的最大增量 Δ = b[i] - c[i]
        // 使用 Long.MIN_VALUE 表示该标签尚未出现
        long[] best = new long[m + 1];
        Arrays.fill(best, Long.MIN_VALUE);

        for (int i = 0; i < n; i++) {
            int t = a[i];
            long delta = b[i] - c[i];
            if (delta > best[t]) best[t] = delta;
        }

        long ans = base;
        // 逐类加入最大非负增量
        for (int t = 1; t <= m; t++) {
            if (best[t] > 0) ans += best[t];
        }

        System.out.println(ans);
    }
}

题目内容

小美正在给自己的物品贴标签。她一共有$m$种不同的标签，每种标签只有一个。 对于第$i$个物品，如果贴上$a_i$号标签，那么它的美观值为$b_i$;如果没有贴上$a_i$号标签，则其美观值为$c_i$。 小美想知道在合理的分配下，所有物品的美观值之和最大为多少。

输入描述

第一行输入两个整数$n$和$m$($1≤n,m≤10^5$)代表小美的物品个数和标签种类。 第二行输入$n$个整数$a_1,a_2,.,a_n$($1≤a_i≤m$)代表每个物品适合的标签种类. 第三行输入$n$个整数$b_1, b_2,..,b_n$($-10^6≤b_i≤10^6$)代表每个物品贴上适合的标签后的美观值。 第四行输入$n$个整数$c1, c2,..,c_n$($-10^6≤c_i≤10^6$)代表每个物品未贴上适合标签时的美观值。

输出描述

在一行上输出一个整数，代表所有物品美观值之和的最大值。

样例1

输入

3 3
1 2 1
5 4 3
-1 2 -100

输出

6

说明

只要把第二个物品贴上$2$号标签，第三个物品贴上$1$号标签，此时美观值之和为$-1+4+3=6$