Day3 - codeforces

碎碎念…昨天在做，感觉有思路，是背包问题，确实没做出来，又看题解。明白到背包问题如何处理顺序问题

1.题目描述

链接：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

输出描述

输出一个整数

2.示例

输入

1 74
502
2
47

输出

408

3.题目分析

这可以理解为背包问题，对于前i道题目，在背包容量为 j 分钟的情况下得到的最大分数，dp[i][j] 表示前[0…i)道题目，j表示总共的时间；

但是，有一个问题，就是顺序问题，我们知道，背包问题本身是组合问题，不是排序的。但是对于这道题来说，先做第一题和先做第二题的分数是不一样的

core12 = maxPoints1 + maxPoints2 – pointsPerMinute1*t1 – pointsPerMinute2*(t1+t2) ; 先做第一题

core21 = maxPoints1 + maxPoints2 – pointsPerMinute1*t2 – pointsPerMinute1*(t1+t2) ; 先做第二题

core12 – core21 = pointsPerMinute1 * t2 – pointsPerMinute2 * t1

当pointsPerMinute1 * t2 > t2 – pointsPerMinute2 * t1 时，先做第一题分数更高；

因此我们可以对每道题的优先级进行排序，先选优先级最高的；为什么呢？顺序选取我们也会选优先级最高的，分数最高，因为初始化直接进行预处理

最后就是变成 0-1 背包问题了

4.代码实现

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;



struct PointNode
{
	long long maxPoint;
	long long pointsPerMinute;
	long long requiredTime;
};

//long long dp[100000 + 5];
int main()
{
	//初始化

	int N, T;
	cin >> N >> T;
	vector<PointNode>Points(N);
	for (int i = 0; i < N; ++i)
		cin >> Points[i].maxPoint;
	for (int i = 0; i < N; ++i)
		cin >> Points[i].pointsPerMinute;
	for (int i = 0; i < N; ++i)
		cin >> Points[i].requiredTime;

	//按照优先级进行排序
	sort(Points.begin(), Points.end(), [](const PointNode& P1, const PointNode& P2)->bool
		{
			return (P1.pointsPerMinute * P2.requiredTime) > (P2.pointsPerMinute * P1.requiredTime);
		});

	vector<vector<long long>>dp(N + 1, vector<long long>(T + 1));
	for (int j = 0; j <= T; ++j)
		dp[0][j] = 0;

	long long res = 0;
	for (int i = 1; i <= N; ++i)
	{
		for (int j = 0; j <= T; ++j)
		{
			//分数是可能减为负数的
			if (j >= Points[i - 1].requiredTime)
				dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - Points[i - 1].requiredTime] + Points[i - 1].maxPoint - Points[i - 1].pointsPerMinute * j);
			else
				dp[i][j] = dp[i - 1][j];
			res = max(res, dp[i][j]);
		}
	}

	cout << res;
	return 0;
}

5.总结

背包问题的时候要注意优先级的问题，能够找到优先级关系，就进行排序选取；

这里的话要注意容量最大的时间未必是最优的，比如50min的容量，但是我40min就做完了，但是计算的乘法因子是50【当然也可以记录消耗的时间】