企业官网建设流程全解析

题目：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 M=17M=17元钱。下面是三种古董的花费和收入。

在这种情况下，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\times4+1\times2=225×(7−3)+1×(4−2)=5×4+1×2=22元。他不能获得比这更多的利润了。

提示：第二个样例很有挑战性，但我们的答案是正确的。

输入格式

• 第1 11行：两个用空格分隔的整数：N NN和M MM。
• 第2 22行到第N + 1 N+1N+1行：第i + 1 i+1i+1行包含两个用空格分隔的整数：C i C_iCi​和R i R_iRi​。

输出格式

• 第1 11行：FJ 在给定成本和收入的情况下可以产生的最大利润。

输入输出样例 #1

输入 #1

3 17 2 4 5 6 3 7

输出 #1

22

说明/提示

（由 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数组扫一遍，减去花费，求最大

代码（一维数组）

#include<bits/stdc++.h>usingnamespacestd;constintM=1e5+10;intn,V,v,w;longlongf[M],ans;intmain(){cin>>n>>V;for(inti=1;i<=n;i++){cin>>v>>w;w-=v;if(w<=0)continue;for(intj=v;j<=V;j++)f[j]=max(f[j],f[j-v]+w);}for(intj=0;j<=V;j++)ans=max(ans,f[j]+V-j);cout<<ans;return0;}

结果