题目P3027 [USACO10OCT] Making Money G题目描述FJ 又经营起了古董生意买卖一些像奶牛圣诞树上的装饰之类的小玩意。他知道他会将他能存储的N ( 1 ≤ N ≤ 100 ) N(1 \le N \le 100)N(1≤N≤100)件不同的奶牛古董每件都卖出。而且如果他的钱足够多他可以买他想要的任意数量的古董即他可以购买的古董数量没有限制。他只有M ( 1 ≤ M ≤ 10 5 ) M(1\le M\le 10^5)M(1≤M≤105)元钱来买古董但他想要在他经商的第一年年末最大化他的利润这有点难以解释。第i ii种古董采购需要花费C i ( 1 ≤ C i ≤ 10 5 ) C_i(1\le C_i \le 10^5)Ci​(1≤Ci​≤105)元钱每卖掉一件可以获得R i ( 1 ≤ R i ≤ 10 5 ) R_i(1\le R_i \le 10^5)Ri​(1≤Ri​≤105)元钱每卖一件的利润为R i − C i R_i-C_iRi​−Ci​。FJ 可以以任意顺序卖出他的货物。他并不需要花光他所有的钱来购买古董。FJ 在他经商的第一年年末能得到的最大总利润利润 初始钱数 - 总花费 总收入是多少呢输入数据保证这个数字不会超过10 9 10^9109。假设 FJ 只有3 33种古董而且开始时有M 17 M17M17元钱。下面是三种古董的花费和收入。古董花费收入124256337在这种情况下FJ 应该花15 1515元购买5 55个3 33号古董再花2 22元购买1 11个1 11号古董总共17 1717元。他的利润是5 × ( 7 − 3 ) 1 × ( 4 − 2 ) 5 × 4 1 × 2 22 5\times(7-3)1\times(4-2)5\times41\times2225×(7−3)1×(4−2)5×41×222元。他不能获得比这更多的利润了。提示第二个样例很有挑战性但我们的答案是正确的。输入格式第1 11行两个用空格分隔的整数N NN和M MM。第2 22行到第N 1 N1N1行第i 1 i1i1行包含两个用空格分隔的整数C i C_iCi​和R i R_iRi​。输出格式第1 11行FJ 在给定成本和收入的情况下可以产生的最大利润。输入输出样例 #1输入 #13 17 2 4 5 6 3 7输出 #122说明/提示由 ChatGPT 4o 翻译思路状态表示f[i][j]是指从前i种古董中选且总花费恰好为j的最大利润每种古董数量无限制所以是完全背包状态转移方程优化1版本f[i][j]max(f[i-1][j],f[i][j-v]w)这里的w是收入-花费输出总利润 初始钱数 - 总花费 总收入f数组存的利润虽然是最大值但是还没有减去花费这就导致f[V]不一定是最大总利润所以要把整个f数组扫一遍减去花费求最大代码一维数组#includebits/stdc.husingnamespacestd;constintM1e510;intn,V,v,w;longlongf[M],ans;intmain(){cinnV;for(inti1;in;i){cinvw;w-v;if(w0)continue;for(intjv;jV;j)f[j]max(f[j],f[j-v]w);}for(intj0;jV;j)ansmax(ans,f[j]V-j);coutans;return0;}结果