[codeforces][dp]
2024-09-01 15:17:35
链接:https://ac.nowcoder.com/acm/problem/21314
来源:牛客网
题目描述
牛牛正在打一场CF
比赛时间为T分钟,有N道题,可以在比赛时间内的任意时间提交代码
第i道题的分数为maxPoints[i],题目的分数随着比赛的进行,每分钟减少pointsPerMinute[i]
这是一场比较dark的Cf,分数可能减成负数
已知第i道题需要花费 requiredTime[i] 的时间解决
请问最多可以得到多少分
比赛时间为T分钟,有N道题,可以在比赛时间内的任意时间提交代码
第i道题的分数为maxPoints[i],题目的分数随着比赛的进行,每分钟减少pointsPerMinute[i]
这是一场比较dark的Cf,分数可能减成负数
已知第i道题需要花费 requiredTime[i] 的时间解决
请问最多可以得到多少分
输入描述:
第一行输入两个整数N,T (1 ≤ N ≤ 50, 1 ≤ T ≤ 100000)
第二行输入n个整数maxPoints[i]
第三行输入n个整数pointsPerMinute[i]
第四行输入n个整数requiredTime[i]
1 ≤ maxPoints[i],pointsPerMinute[i],requiredTime[i] ≤ 100000
输出描述:
输出一个整数
示例1
输入
1 74
502
2
47
输出
408
示例2
输入
2 40000
100000 100000
1 100000
50000 30000
输出
0
示例3
输入
3 75
250 500 1000
2 4 8
25 25 25
输出
1200
示例4
输入
3 30
100 100 100000
1 1 100
15 15 30
输出
97000
备注:
子任务1: n <= 10
子任务2: n <= 20
子任务3: 无限制
题意:给出一些任务,每个任务都有一个初始分ai,每分钟会降低bi(可以降低到负分),完成这个任务需要花费ci分钟,求最多可以得到的分数
题解:容易看出是个dp,又由于bi影响着ai每个时刻的值,所以做任务的顺序影响着dp结果,想要得到最优的dp结果就需要进行排序,假设有两个任务1和2,那么二者可以得到的分数为如果先做1,则=a1+a2-b1*c1-b2*(c1+c2),如果先做2,则=a1+a2-b2*c2-b1*(c1+c2),则排序条件就应该是a1+a2-b1*c1-b2*(c1+c2)>a1+a2-b2*c2-b1*(c1+c2)
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
struct pot{
ll q;
ll w;
ll e;
}p[];
bool cmp(struct pot aa,struct pot bb){
return (aa.e+bb.e)*bb.w+aa.e*aa.w<(aa.e+bb.e)*aa.w+bb.e*bb.w;
}
ll dp[];
int main()
{
ll n,t;
scanf("%lld%lld",&n,&t);
for(int i=;i<=n;i++){
scanf("%lld",&p[i].q);
}
for(int i=;i<=n;i++){
scanf("%lld",&p[i].w);
}
for(int i=;i<=n;i++){
scanf("%lld",&p[i].e);
}
ll ans=;
sort(p+,p++n,cmp);
for(int i=;i<=n;i++){
for(int j=t;j>=p[i].e;j--){
dp[j]=max(dp[j],dp[j-p[i].e]+p[i].q-(p[i].w)*(j));
ans=max(ans,dp[j]);
}
}
printf("%lld\n",ans);
return ;
}
最新文章
- [2014.01.27]wfTextImage 文字图像组件 1.6
- Dynamic V Strongly Typed Views
- Quartz应用实践入门案例一(基于Web环境)
- ECshop 怎样修改商品详细页的“浏览次数”
- 三种查看SqlServer中数据物理pge页的方法
- [HackerCup Round1 2] Autocomplete (Trie)
- Solr单机部署和集群部署
- 1081. Rational Sum (20)
- mysql 安装-编码
- [转]RecyclerView初探
- easyui实现权限管理
- PHP实现畅言留言板和网易跟帖样式
- VR全景智慧城市,开启“上帝视角”体验‘身临其境’
- volt问题
- http 状态表
- go语言打造p2p网络
- 分享几个写 demo 的思路
- Tensorflow-hub[例子解析1]
- 【Git】简单使用
- PHP如何动态传入参数