[CSP-J 2019] 纪念品

知识点

动态规划、完全背包、决策优化

解题思路

把跨越多天持有商品看作每天先卖出再按同价买回，持仓和金币不变。因此只需依次优化相邻两天的交易。设当天可用金币为money，商品j的背包费用为当天价格，价值为次日价格减当天价格。对于有正收益的商品执行完全背包，dp[c]表示最多花费c金币可获得的最大利润；容量正序遍历允许购买任意件。当天结束后将dp[money]加入金币，再处理下一对相邻日期。

正确性说明

每天先卖出再买回是等价操作，任何多日持仓方案都能按相邻日期拆分而不改变财富。同一日期中，多余金币可保留，能买的每种商品数量无上限，因此完全背包恰好覆盖所有可行的隔夜投资组合。更多金币总可通过保留余额模仿较少金币的策略，不会使后续最优值降低；逐日取最大金币即可得到最终最优解。

易错点

背包容量由当前金币决定，每天重新初始化利润数组；完全背包容量必须正序；非正利润商品可直接跳过；T=1时没有交易，输出初始金币。不能用利润率贪心替代整数背包。

复杂度

设C为任意一天的金币上界（题目保证C≤10000），时间O(TNC)，背包额外空间O(C)，价格表空间O(TN)。

参考代码（GNU C++17）

#include<bits/stdc++.h>
using namespace std;
int main(){
    ios::sync_with_stdio(false); cin.tie(nullptr);
    int T,N,money; cin>>T>>N>>money;
    vector<vector<int>> p(T,vector<int>(N));
    for(auto &row:p) for(int &x:row) cin>>x;
    for(int day=0;day+1<T;++day){
        vector<int> dp(money+1,0);
        for(int j=0;j<N;++j){
            int cost=p[day][j],gain=p[day+1][j]-cost;
            if(gain<=0) continue;
            for(int c=cost;c<=money;++c)
                dp[c]=max(dp[c],dp[c-cost]+gain);
        }
        money+=dp[money];
    }
    cout<<money<<'\n';
    return 0;
}