算法思路

核心思想：按费用分组 + 斜率优化

1. 分组处理：由于物品的费用C_i ≤ 300，我们可以将所有物品按照费用c分组，每组内按照价值v从大到小排序。

2. 状态设计：设dp[i]表示使用i万元能获得的最大吸引力值。

3. 分组转移：对于每个费用组(c, items)，我们考虑从当前状态dp[j]转移到dp[j + k*c]（k表示选择该组的几个物品）。

4. 单调队列优化：对于每个余数r（0 ≤ r < c），我们考虑所有满足j ≡ r (mod c)的状态。转移可以看作：

   dp[j] = max{ dp[j - k*c] + sum(v[1..k]) }
   

   这可以通过单调队列维护一个滑动窗口的最大值来优化。

算法步骤

1. 将物品按费用分组，每组内按价值降序排序
2. 对每个费用组：
   • 对每个余数r (0 ≤ r < c)：
     • 构建单调队列
     • 遍历所有j ≡ r (mod c)且j ≤ K的状态
     • 维护窗口大小为c的滑动区间最大值
3. 输出dp[1..K]

时间复杂度

• 分组排序：O(300 × NlogN) 但实际很小
• 动态规划：O(K × 300)，因为每个余数最多处理K/c个状态，总复杂度O(300K)

C++代码实现

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

typedef long long ll;
const int MAXK = 50005;
const int MAXC = 305;

ll dp[MAXK];
vector<ll> items[MAXC];
int N, K;

int main() {
    scanf("%d%d", &N, &K);
    
    // 读入数据并按费用分组
    for (int i = 0; i < N; i++) {
        int c; ll v;
        scanf("%d%lld", &c, &v);
        items[c].push_back(v);
    }
    
    // 对每组物品按价值降序排序
    for (int c = 1; c <= 300; c++) {
        if (items[c].empty()) continue;
        sort(items[c].rbegin(), items[c].rend());
    }
    
    // 初始化DP数组
    memset(dp, 0, sizeof(dp));
    
    // 对每个费用组进行转移
    for (int c = 1; c <= 300; c++) {
        if (items[c].empty()) continue;
        
        // 预处理前缀和
        vector<ll> prefix = {0};
        for (int i = 0; i < items[c].size(); i++) {
            prefix.push_back(prefix.back() + items[c][i]);
        }
        
        // 对每个余数分别处理
        for (int r = 0; r < c; r++) {
            deque<int> dq;
            
            for (int j = 0; j * c + r <= K; j++) {
                int idx = j * c + r;
                if (idx > K) break;
                
                // 维护单调队列
                while (!dq.empty() && dp[dq.back() * c + r] - prefix[dq.back()] <= 
                       dp[idx] - prefix[j]) {
                    dq.pop_back();
                }
                dq.push_back(j);
                
                // 移除超出窗口的元素
                while (!dq.empty() && j - dq.front() > items[c].size()) {
                    dq.pop_front();
                }
                
                // 更新DP值
                if (!dq.empty()) {
                    int best_j = dq.front();
                    dp[idx] = max(dp[idx], dp[best_j * c + r] + prefix[j - best_j]);
                }
            }
        }
    }
    
    // 输出结果
    for (int i = 1; i <= K; i++) {
        printf("%lld%c", dp[i], i == K ? '\n' : ' ');
    }
    
    return 0;
}

关键优化点

1. 利用c_i范围小：将300种费用分别处理，避免O(NK)复杂度
2. 单调队列：将分组背包的O(K²)优化到O(K)
3. 前缀和预处理：快速计算选择多个同费用物品的总价值

这种优化方法在c_i范围较小的背包问题中非常有效，是处理大规模背包问题的经典技巧。