CSP-J 2019纪念品题解（洛谷P5662）：动态规划+完全背包问题的实战应用

一、题目解读

2019年CSP-J的“纪念品”问题（对应洛谷P5662）要求玩家在T天内通过买卖纪念品最大化金币收益。每天可交易N种商品，需计算最优策略下的最终金币数。题目强调动态规划思维与资源分配优化，是算法竞赛中的经典题型。

二、解题思路

核心思路为“动态规划+完全背包问题”。每天将当前商品价格与次日差价视为“物品价值”，通过滚动计算次日可获得的“最大收益背包”，动态更新总金币数。关键在于将“连续两天的差价利润”转化为可重复选择的“背包物品”，利用dp[i]（i金币时的最大收益）实现状态转移。

三、解题步骤

1. 输入处理：读取天数T、商品数N、初始金币M及每日价格矩阵。

2. 外层循环遍历T-1天（最后一天无法交易）。

3. 内层循环处理当日商品：计算差价profit，仅对正利润商品执行完全背包更新（避免无利操作）。

4. 状态转移方程：dp[j]=max(dp[j],dp[j-cost]+profit)，实现“用剩余金币重复购买差价商品”的逻辑。

5. 每日结束后，将dp[M]累加到总金币M，滚动优化。

四、代码与注释

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr); // 优化输入效率
    
    int T, N, M;
    cin >> T >> N >> M; // 输入天数、商品数、初始金币
    
    vector<vector<int>> prices(T, vector<int>(N)); // 价格矩阵
    for (int i = 0; i < T; ++i) {
        for (int j = 0; j < N; ++j) {
            cin >> prices[i][j];
        }
    }
    
    // 每天处理时，计算当天到第二天的最大收益
    for (int day = 0; day < T - 1; ++day) {
        vector<int> dp(M + 1, 0); // dp[i]表示i金币能获得的最大收益
        
        for (int item = 0; item < N; ++item) {
            int cost = prices[day][item];
            int profit = prices[day + 1][item] - cost; // 次日差价
            
            if (profit <= 0) continue; // 无利可图则跳过
            
            // 完全背包问题解法
            for (int j = cost; j <= M; ++j) { // 从成本开始累加
                dp[j] = max(dp[j], dp[j - cost] + profit); // 状态转移
            }
        }
        
        // 更新最大金币数
        M += dp[M];
    }
    
    cout << M << endl; // 输出最终金币
    return 0;
}

五、总结

该解法巧妙将“连续两天的利润”抽象为可重复选择的“背包物品”，通过动态规划规避了复杂的路径搜索。关键在于识别问题中的“资源可重复利用”特性，并应用完全背包模型简化计算。对算法竞赛中的资源分配类问题具有重要参考价值。