#include<iostream> #include<cstring> using namespace std; const int N=105,M=10005; int c[N][N],dp[M],w[N][N],t,n,m; int main(){ cin>>t>>n>>m; for(int i=1;i<=t;i++) for(int j=1;j<=n;j++) cin>>c[i][j]; for(int i=1;i<t;i++){ memset(dp,0,sizeof(dp)); for(int j=1;j<=n;j++){ int v=c[i][j],w=c[i+1][j]-c[i][j]; for(int k=v;k<=m;k++) dp[k]=max(dp[k],dp[k-v]+w); } m=max(dp[m]+m,m); } cout<<m; return 0; }

题目大意 未来有 T 天，每天可以无限次买入或卖出任意一种纪念品。 初始有 M 枚金币。 每天买入和卖出的价格是相同的。 第 T 天必须将手中所有纪念品卖出，换回金币。 目标是最大化第 T 天结束时的金币总数。 关键点: 交易可以无限次进行，意味着我们可以在一天内买入、卖出、再买入…… 每次交易利润 = 卖出价 - 买入价，所以我们可以把问题转化为在相邻两天之间寻找“差价”并进行“套利”。 因为可以在一天内无限次交易，所以我们可以将问题简化为在每一天与下一天之间进行“最大套利”操作。 解题思路（贪心 + 多重背包） 我们可以将问题拆解为： 对于每一天 i（从第1天到第 T-1 天），我们考虑从第 i 天到第 i+1 天之间的交易。 对于每种纪念品 j，如果 P[i+1][j]>P[i][j] ，则我们可以买入第 i 天的纪念品，在第 i+1 天卖出，获得差价利润。 所以每一天可以看作是一个多重背包问题，即我们用当前的金币，尽可能多地买入那些“明天价格更高”的纪念品，然后在第二天卖出，获得利润。 算法选择 对于每一天 i，我们构建一个“套利背包”： 每个物品的“成本”是 P[i][j]，收益是 P[i+1][j] - p[i][j] 我们的目标是用当前的金币尽可能多地买入这些“有利可图”的纪念品 使用完全背包模型（因为每个纪念品可以无限买入） 每天更新金币数为：当前金币 + 最大利润 三、信奥知识教授 与信奥相关的知识点 完全背包问题：每个物品可以选无限次，适合本题“无限次交易”的设定。 状态压缩与动态规划：每天的状态只依赖前一天，可以用滚动数组优化空间。 贪心思想：只关注有正利润的交易机会。 时间复杂度分析：最多 T=100 天，每种纪念品价格最大为 10^4 ，金币最大为 10^4 ，所以每轮背包复杂度是 O(MN)，总复杂度 O(TMN) 是可以接受的。 正解：

#include<iostream> #include<cstring> using namespace std; const int N=105,M=10005; int c[N][N],dp[M],w[N][N],t,n,m; int main(){ cin>>t>>n>>m; for(int i=1;i<=t;i++) for(int j=1;j<=n;j++) cin>>c[i][j]; for(int i=1;i<t;i++){ memset(dp,0,sizeof(dp)); for(int j=1;j<=n;j++){ int v=c[i][j],w=c[i+1][j]-c[i][j]; for(int k=v;k<=m;k++) dp[k]=max(dp[k],dp[k-v]+w); } m=max(dp[m]+m,m); } cout<<m; return 0; }