能量石贪心+DP
传送门:能量石
相关题目:耍杂技的牛,国王游戏
思路:由贪心可证得相邻两个能量石的顺序不同时获得的收益也是不同的,所以需要s*x.l<x.s*l
之后则是一个01背包问题,需要注意这里f[j]的采用的是恰好为j,需要初始化f为负无穷,f[0]=0;
代码:
-
#include<iostream>
-
#include<cstring>
-
#include<algorithm>
-
using namespace std;
-
typedef long long LL;
-
const int N=10010,mod=1e9 7;
-
int f[N],g[N];
-
int n,m;
-
struct node
-
{
-
int s,e,l;
-
bool operator<(const node &x) const
-
{
-
return s*x.l<x.s*l;
-
}
-
}d[N];
-
-
int main()
-
{
-
int t;
-
cin>>t;
-
for(int p=1;p<=t;p )
-
{
-
cin>>n;
-
memset(f,-0x3f,sizeof f);
-
int s,e,l;
-
int sum=0;
-
for(int i=1;i<=n;i )
-
{
-
cin>>s>>e>>l;
-
sum =s;
-
d[i]={s,e,l};
-
}
-
sort(d 1,d n 1);
-
f[0]=0;
-
for(int i=1;i<=n;i )
-
for(int j=sum;j>=d[i].s;j--)
-
{
-
f[j]=max(f[j],f[j-d[i].s] max(0,d[i].e-(j-d[i].s)*d[i].l));
-
//cout<<f[j]<<endl;
-
}
-
int res=0;
-
for(int i=0;i<=sum;i )
-
res=max(res,f[i]);
-
-
printf("Case #%d: %d\n",p,res);
-
}
-
return 0;
-
}
这篇好文章是转载于:学新通技术网
- 版权申明: 本站部分内容来自互联网,仅供学习及演示用,请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系,请提供相关证据及您的身份证明,我们将在收到邮件后48小时内删除。
- 本站站名: 学新通技术网
- 本文地址: /boutique/detail/tanhhafjba
系列文章
更多
同类精品
更多
-
photoshop保存的图片太大微信发不了怎么办
PHP中文网 06-15 -
《学习通》视频自动暂停处理方法
HelloWorld317 07-05 -
word里面弄一个表格后上面的标题会跑到下面怎么办
PHP中文网 06-20 -
Android 11 保存文件到外部存储,并分享文件
Luke 10-12 -
photoshop扩展功能面板显示灰色怎么办
PHP中文网 06-14 -
微信公众号没有声音提示怎么办
PHP中文网 03-31 -
excel下划线不显示怎么办
PHP中文网 06-23 -
excel打印预览压线压字怎么办
PHP中文网 06-22 -
TikTok加速器哪个好免费的TK加速器推荐
TK小达人 10-01 -
怎样阻止微信小程序自动打开
PHP中文网 06-13