题解 | #牛牛的背包#

#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <climits>
using namespace std;
typedef long long LL;

int main() {
    int n;
    cin >> n;
    
    vector<int> type(n), taste(n);
    for (int i = 0; i < n; i++) cin >> type[i];
    for (int i = 0; i < n; i++) cin >> taste[i];
    
    // 1. 将物品按类型分组
    map<int, vector<int>> groups;
    for (int i = 0; i < n; i++) {
        groups[type[i]].push_back(taste[i]);
    }
    
    // 2. 对每组物品按taste降序排序，并计算前缀和
    // typeSums存储每组的前缀和数组
    vector<vector<LL>> typeSums;
    for (auto& p : groups) {
        auto& v = p.second;
        // 降序排序
        sort(v.rbegin(), v.rend());
        
        // 计算前缀和，sums[i]表示选前i个物品的taste总和
        vector<LL> sums(v.size() + 1, 0);
        for (int i = 0; i < v.size(); i++) {
            sums[i + 1] = sums[i] + v[i];
        }
        typeSums.push_back(sums);
    }
    
    int m = typeSums.size();  // 物品种类数
    
    // 3. 动态规划
    // dp[k]表示恰好选择k种类型时的最大taste总和
    vector<LL> dp(m + 1, LLONG_MIN);
    dp[0] = 0;  // 不选任何物品
    
    // 分组背包：遍历每个类型（分组）
    for (const auto& sums : typeSums) {
        int cnt = sums.size() - 1;  // 该组物品数量
        
        // 逆序遍历k，确保每组只被选一次
        for (int k = m; k >= 1; k--) {
            // 枚举从该组中选择的物品数量t（至少选1个才能算作选择了该类）
            for (int t = 1; t <= cnt; t++) {
                if (dp[k - 1] != LLONG_MIN) {
                    dp[k] = max(dp[k], dp[k - 1] + sums[t]);
                }
            }
        }
    }
    
    // 4. 计算答案
    LL ans = 0;  // 至少为0（不选任何物品）
    for (int k = 0; k <= m; k++) {
        if (dp[k] != LLONG_MIN) {
            ans = max(ans, k * dp[k]);
        }
    }
    
    cout << ans << endl;
    return 0;
}