【洛谷P2647】最大收益
2024-09-05 17:37:43
题目大意
现在你面前有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)。
题解
同 洛谷P1417。
只不过在计算答案贡献时,发现正序枚举的时间复杂度是 \(O(N^3)\),即:决策的时间复杂度达到了 \(O(N)\)。在这里可以采用对物品进行逆向排序,这样每次选择的时候,将当前决策的物品作为第一个选择的物品,可以发现,这对后面物品对答案的贡献减少了 \(val*(j-1)\),即可在 \(O(1)\) 决策。
代码如下
#include <bits/stdc++.h>
using namespace std;
const int maxn=3010;
int n,dp[maxn][maxn];
struct node{int r,w;}a[maxn];
bool cmp(const node &x,const node &y){
return x.r>y.r;
}
void read_and_parse(){
scanf("%d",&n);
for(int i=1;i<=n;i++)scanf("%d%d",&a[i].w,&a[i].r);
sort(a+1,a+n+1,cmp);
}
void solve(){
for(int i=1;i<=n;i++)
for(int j=1;j<=i;j++)
dp[i][j]=max(dp[i-1][j],dp[i-1][j-1]+a[i].w-(j-1)*a[i].r);
int ans=0;
for(int i=1;i<=n;i++)ans=max(ans,dp[n][i]);
printf("%d\n",ans);
}
int main(){
read_and_parse();
solve();
return 0;
}
最新文章
- [No000057]一个人默默背单词,小心被传染哦
- Command模式
- OC基础-第1天
- 类似a:hover的伪类的注解
- UrlDownloadFile, 线程下载文件, 带进度条
- POJ 1182 食物链(并查集拆点)
- Eclipse更改默认工作目录的方法
- NLP | 自然语言处理 - 标注问题与隐马尔科夫模型(Tagging Problems, and Hidden Markov Models)
- dubbo结构及通信简介
- SQL中内连接和外连接的区别
- 11、OpenCV实现图像的灰度变换
- FastJson序列化Json自定义返回字段,普通类从spring容器中获取bean
- poj 2976(二分搜索+最大化平均值)
- MySQL四种事务隔离级别详解
- postman中 form-data、x-www-form-urlencoded、raw、binary的区别--转
- java 集合(四)HashSet 与 LinkedHashSet
- angularjs的路由ui.router
- DQL-条件查询
- 状压搜索 洛谷T47092 作业
- [计算机网络-应用层] DNS:因特网的目录服务
热门文章
- Reactjs之Axios、fetch-jsonp获取后台数据
- 【HANA系列】SAP 一位SAP培训顾问的建议:SAP HANA应该如何学习?
- python学习之数据类型(set)
- LeetCode.961-2N数组中N次重复的元素(N-Repeated Element in Size 2N Array)
- P4878 [USACO05DEC] 布局
- python3 selenuim PC端使用chrome模拟手机进行H5自动化
- VMware下的Centos7联网并设置固定IP(nat)
- 关于ElementUI中日期选择器时间选择范围限制
- [转帖]Linux下批量替换文件内容方法
- [转帖]Spring Cloud底层原理