参考：
总结
本系列为CSP-J/S算法竞赛真题讲解，会按照年份分析每年的真题，并给出对应的答案。本文为2019年真题。
https://www.luogu.com.cn/problem/list?tag=343&page=1
[CSP-J2019] 纪念品
题目描述
小伟突然获得一种超能力，他知道未来 T TT 天 N NN 种纪念品每天的价格。某个纪念品的价格是指购买一个该纪念品所需的金币数量，以及卖出一个该纪念品换回的金币数量。
每天，小伟可以进行以下两种交易无限次：
- 任选一个纪念品，若手上有足够金币，以当日价格购买该纪念品；
- 卖出持有的任意一个纪念品，以当日价格换回金币。
每天卖出纪念品换回的金币可以立即用于购买纪念品，当日购买的纪念品也可以当日卖出换回金币。当然，一直持有纪念品也是可以的。
T TT 天之后，小伟的超能力消失。因此他一定会在第 T TT 天卖出所有纪念品换回金币。
小伟现在有 M MM 枚金币，他想要在超能力消失后拥有尽可能多的金币。
输入格式
第一行包含三个正整数 T , N , M T, N, MT,N,M，相邻两数之间以一个空格分开，分别代表未来天数 T TT，纪念品数量 N NN，小伟现在拥有的金币数量 M MM。
接下来 T TT 行，每行包含 N NN 个正整数，相邻两数之间以一个空格分隔。第 i ii 行的 N NN 个正整数分别为 P i , 1 P_{i,1}Pi,1，P i , 2 P_{i,2}Pi,2,……,P i , N P_{i,N}Pi,N，其中 P i , j P_{i,j}Pi,j 表示第 i ii 天第 j jj 种纪念品的价格。
输出格式
输出仅一行，包含一个正整数，表示小伟在超能力消失后最多能拥有的金币数量。
样例 #1
样例输入 #1
6 1 100 50 20 25 20 25 50
样例输出 #1
305
样例 #2
样例输入 #2
3 3 100 10 20 15 15 17 13 15 25 16
样例输出 #2
217
提示
【输入输出样例 1 说明】
最佳策略是：
第二天花光所有 100 枚金币买入 5 个纪念品 1；
第三天卖出 5 个纪念品 1，获得金币 125 枚；
第四天买入 6 个纪念品 1，剩余 5 枚金币；
第六天必须卖出所有纪念品换回 300 枚金币，第四天剩余 5 枚金币,共 305 枚金币。
超能力消失后，小伟最多拥有 305 枚金币。
【输入输出样例 2 说明】
最佳策略是：
第一天花光所有金币买入 10 个纪念品 1；
第二天卖出全部纪念品 1 得到 150 枚金币并买入 8 个纪念品 2 和 1 个纪念品 3，剩余 1 枚金币；
第三天必须卖出所有纪念品换回216 枚金币，第二天剩余1枚金币，共 217 枚金币。
超能力消失后，小伟最多拥有 217 枚金币。
【数据规模与约定】
对于 10 % 10\%10% 的数据，T = 1 T = 1T=1。
对于 30 % 30\%30% 的数据，T ≤ 4 , N ≤ 4 , M ≤ 100 T \leq 4, N \leq 4, M \leq 100T≤4,N≤4,M≤100，所有价格 10 ≤ P i , j ≤ 100 10 \leq P_{i,j} \leq 10010≤Pi,j≤100。
另有 15 % 15\%15% 的数据，T ≤ 100 , N = 1 T \leq 100, N = 1T≤100,N=1。
另有 15 % 15\%15% 的数据，T = 2 , N ≤ 100 T = 2, N \leq 100T=2,N≤100。
对于 100 % 100\%100% 的数据，T ≤ 100 , N ≤ 100 , M ≤ 1 0 3 T \leq 100, N \leq 100, M \leq 10^3T≤100,N≤100,M≤103，所有价格 1 ≤ P i , j ≤ 1 0 4 1 \leq P_{i,j} \leq 10^41≤Pi,j≤104，数据保证任意时刻，小明手上的金币数不可能超过 1 0 4 10^4104。
答案
#include <iostream> #include <memory.h> using namespace std; const int N = 101; const int M = 10001; int n, m, t, price[N][N], f[M]; int main() { cin >> t >> n >> m; for(int i = 1; i <= t; i++) for(int j = 1; j <= n; j++) cin >> price[j][i]; //读入每种商品每天的价格 for(int k = 1; k < t; k++) { memset(f, 0, sizeof f);//每轮开始前都要制零 for(int i = 1; i <= n; i++) for(int j = price[i][k]; j <= m; j++)//完全背包,正着循环 f[j] = max(f[j], f[j - price[i][k]] + price[i][k + 1] - price[i][k]); m += f[m];//加上盈利的钱，进入下一轮买卖 } cout << m; return 0; }
输出为:
现场真题注意事项
https://cspoj.com/contest.php?cid=1002
Fus5yz4x3EcSJH1Z
注意事项
- 文件名（程序名和输入输出文件名）必须使用英文小写。（提交必须使用freopen()进行提交）
- C/C++ 中函数 main() 的返回值类型必须是 int，程序正常结束时的返回值必须是0。
- 提交的程序代码文件的放置位置请参考各省的具体要求。
- 因违反以上三点而出现的错误或问题，申述时一律不予受理。
- 若无特殊说明，结果的比较方式为全文比较（过滤行末空格及文末回车）。
- 程序可使用的栈空间内存限制与题目的内存限制一致。
- 全国统一评测时采用的机器配置为：Inter® Core™ i7-8700K CPU @3.70GHz，内存 32GB。上述时限以此配置为准。
- 只提供 Linux 格式附加样例文件。
- 评测在当前最新公布的 NOI Linux 下进行，各语言的编译器版本以此为准
/*
假设输入样例数据存在文件test.in中，输出样例数据存在文件test.out中，
则在CSP、NOI等比赛的代码中，需添加freopen、fclose语句，
内容详见模板代码如下。
*/
#include <bits/stdc++.h> #include<cstdio>//必须包含cstdio头文件 #include<iostream> using namespace std; int main(){ freopen("test.in","r",stdin); freopen("test.out","w",stdout); cout<<"Hello NOI"<<endl; fclose(stdin); fclose(stdout); return 0; }
下面为函数的简介，详细可参见 http://www.cplusplus.com/reference/clibrary/cstdio/freopen.html
函数名：freopen
声明：FILE *freopen( const char *path, const char *mode, FILE *stream );
所在文件： stdio.h
参数说明：
path: 文件名，用于存储输入输出的自定义文件名。
mode: 文件打开的模式。和fopen中的模式（如r-只读, w-写）相同。
stream: 一个文件，通常使用标准流文件。
返回值：成功，则返回一个path所指定文件的指针；失败，返回NULL。（一般可以不使用它的返回值）
功能：实现重定向，把预定义的标准流文件定向到由path指定的文件中。标准流文件具体是指stdin、stdout和stderr。其中stdin是标准输入流，默认为键盘；stdout是标准输出流，默认为屏幕；stderr是标准错误流，一般把屏幕设为默认。通过调用freopen，就可以修改标准流文件的默认值，实现重定向。
#include<iostream> #include<cstdio> using namespace std; int main(){ freopen("7532.in", "r", stdin); freopen("7532.out", "w", stdout); //原来的代码保持不变 double a, b, r; int k; cin >> a >> b; k = int(a/b); r = a - b * k; printf("%g", r); //------------- fclose(stdin); fclose(stdout); return 0; }
