[luogu P2647] 最大收益(贪心+dp)
2018-06-17 23:39:07来源:未知 阅读 ()
题目传送门:https://www.luogu.org/problem/show?pid=2647
题目描述
现在你面前有n个物品,编号分别为1,2,3,……,n。你可以在这当中任意选择任意多个物品。其中第i个物品有两个属性Wi和Ri,当你选择了第i个物品后,你就可以获得Wi的收益;但是,你选择该物品以后选择的所有物品的收益都会减少Ri。现在请你求出,该选择哪些物品,并且该以什么样的顺序选取这些物品,才能使得自己获得的收益最大。
注意,收益的减少是会叠加的。比如,你选择了第i个物品,那么你就会获得了Wi的收益;然后你又选择了第j个物品,你又获得了Wj-Ri收益;之后你又选择了第k个物品,你又获得了Wk-Ri-Rj的收益;那么你获得的收益总和为Wi+(Wj-Ri)+(Wk-Ri-Rj)。
输入输出格式
INPUT:
第一行一个正整数n,表示物品的个数。
接下来第2行到第n+1行,每行两个正整数Wi和Ri,含义如题目所述。
OUTPUT:
输出仅一行,表示最大的收益。
输入输出样例
输入样例#1:
2 5 2 3 5
输出样例#1:
6
//样例解释:我们可以选择1号物品,获得了5点收益;之后我们再选择2号物品,获得3-2=1点收益。最后总的收益值为5+1=6。
说明
20%的数据满足:n<=5,0<=Wi,Ri<=1000。
50%的数据满足:n<=15,0<=Wi,Ri<=1000。
100%的数据满足:n<=3000,0<=Wi,Ri<=200000。
SOLUTION 1:暴力枚举出每个物品选或不选,生成物品选取顺序的全排列,暴力求最优解。时间复杂度O(2^n*n!)。期望得分20分。
SOLUTION 2:不难发现我们可以对题目进行一个等价的转换,即倒序选取,选取第 i 件物品会使之前所有选取的物品收益减少Ri。
由此可以得出贪心策略:首先对所有物品按照R由大到小排序,枚举每个物品选或不选,求出最优解。
时间复杂度O(2^n)。期望得分50分。
SOLUTION 3:受SOL2启发,我们可以设计一个动态规划策略,f[i][j] 表示前 i 个物品取 j 个的最大收益,
不难发现其状态转移方程为:f[i][j]=max(f[i-1][j],f[i-1][j-1]+w[i]-r[i]*(j-1)) ,
边界条件f[1][1]=w[1] f[1][0]=0 ,其中物品按照R由小到大排序,
ans=max(f[n][i]) ,
时间复杂度O(n^2),期望得分100分。
1 #include <cstdio> 2 #include <iostream> 3 #include <algorithm> 4 using namespace std; 5 6 struct thing { 7 int a,b; 8 } e[3050]; 9 10 bool cmp(const thing x,const thing y) { 11 return x.b>y.b; 12 } 13 14 int n,ans,f[3005][3005]; 15 16 int main() { 17 scanf("%d",&n); 18 for (int i=1; i<=n; i++) scanf("%d%d",&e[i].a,&e[i].b); 19 sort(e+1,e+n+1,cmp); 20 f[1][0]=0; 21 f[1][1]=e[1].a; 22 for (int i=2; i<=n; i++) { 23 for (int j=1; j<=i; j++) 24 f[i][j]=max(f[i-1][j],f[i-1][j-1]+e[i].a-e[i].b*(j-1)); 25 } 26 for (int i=1; i<=n; i++) ans=max(ans,f[n][i]); 27 printf("%d",ans); 28 }
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
- 【题解】Luogu1739 表达式括号匹配 2020-04-07
- 动态规划:最大子串和 2020-01-30
- 最小割最大流定理&残量网络的性质 2019-12-17
- 不一样的LCA——luoguP1852跳跳棋 2019-11-13
- LuoguP3069 【[USACO13JAN]牛的阵容Cow Lineup 2019-10-30
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash