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

ftggdnt

一、题目解读

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

二、解题思路

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

三、解题步骤

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

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

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

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

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

四、代码与注释

1. #include <iostream>
   
2. #include <vector>
   
3. #include <algorithm>
   
4. using namespace std;
   
5. 
   
6. int main() {
   
7.     ios::sync_with_stdio(false);
   
8.     cin.tie(nullptr); // 优化输入效率
   
9.    
   
10.     int T, N, M;
    
11.     cin >> T >> N >> M; // 输入天数、商品数、初始金币
    
12.    
    
13.     vector<vector<int>> prices(T, vector<int>(N)); // 价格矩阵
    
14.     for (int i = 0; i < T; ++i) {
    
15.         for (int j = 0; j < N; ++j) {
    
16.             cin >> prices[i][j];
    
17.         }
    
18.     }
    
19.    
    
20.     // 每天处理时，计算当天到第二天的**收益
    
21.     for (int day = 0; day < T - 1; ++day) {
    
22.         vector<int> dp(M + 1, 0); // dp[i]表示i金币能获得的**收益
    
23.         
    
24.         for (int item = 0; item < N; ++item) {
    
25.             int cost = prices[day][item];
    
26.             int profit = prices[day + 1][item] - cost; // 次日差价
    
27.             
    
28.             if (profit <= 0) continue; // 无利可图则跳过
    
29.             
    
30.             // 完全背包问题解法
    
31.             for (int j = cost; j <= M; ++j) { // 从成本开始累加
    
32.                 dp[j] = max(dp[j], dp[j - cost] + profit); // 状态转移
    
33.             }
    
34.         }
    
35.         
    
36.         // 更新**金币数
    
37.         M += dp[M];
    
38.     }
    
39.    
    
40.     cout << M << endl; // 输出最终金币
    
41.     return 0;
    
42. }

复制代码

五、总结

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

来源：CSP题解