链接：https://ac.nowcoder.com/acm/problem/21314来源：牛客网
题目描述
牛牛正在打一场CF
比赛时间为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)
1 #include<bits/stdc++.h>
2 using namespace std;
3 typedef
long long ll;
4 struct pot{
5 ll q;
6 ll w;
7 ll e;
8 }p[
55];
9 bool cmp(
struct pot aa,
struct pot bb){
10 return (aa.e+bb.e)*bb.w+aa.e*aa.w<(aa.e+bb.e)*aa.w+bb.e*
bb.w;
11 }
12 ll dp[
100005];
13 int main()
14 {
15 ll n,t;
16 scanf(
"%lld%lld",&n,&
t);
17 for(
int i=
1;i<=n;i++
){
18 scanf(
"%lld",&
p[i].q);
19 }
20 for(
int i=
1;i<=n;i++
){
21 scanf(
"%lld",&
p[i].w);
22 }
23 for(
int i=
1;i<=n;i++
){
24 scanf(
"%lld",&
p[i].e);
25 }
26 ll ans=
0;
27 sort(p+
1,p+
1+
n,cmp);
28 for(
int i=
1;i<=n;i++
){
29 for(
int j=t;j>=p[i].e;j--
){
30 dp[j]=max(dp[j],dp[j-p[i].e]+p[i].q-(p[i].w)*
(j));
31 ans=
max(ans,dp[j]);
32 }
33 }
34 printf(
"%lld\n",ans);
35 return 0;
36 }
View Code
转载于:https://www.cnblogs.com/MekakuCityActor/p/10826388.html
