NC223538. HangGliding
描述
输入描述
The first input line contains two integers: t (1 ≤ t ≤ 10000), indicating the number of tasks, and p(3 ≤ p ≤ 100), indicating the number of pilots.
The next t input lines contain the task descriptions. Each line contains three integers (s, e, and a) separated by a space: 0 ≤ s < e ≤ 10000, s is the start time of the task, and $e$ is the end time of the task, in minutes after the competition starts; a (1 ≤ a ≤ 100) is the number of points awarded for the task. Note that the task start times and end times are non-inclusive, i.e., if a task ends at time T and another task starts at time T, a pilot can compete in both tasks.
After the task descriptions, there are t lines for each pilot. The first t lines in this section are the probabilities of success for each task for pilot 1; the next t lines are the probabilities of success for pilot 2, and so on. The probabilities are floating point numbers in the range 0 to 1, inclusive.
输出描述
Print the top 3 pilots. Print, in order of descending expected score, the pilot’s number, a space, and the pilot’s expected score, rounded to 2 decimal places (i.e., a score of 42.494 would be printed as 42.49; a score of 42.495 would be printed as 42.50). Note that pilots are numbered starting at 1, not zero.
示例1
输入:
3 3 0 1 5 1 2 10 2 3 15 0.0 0.0 0.2 1.0 0.0 0.0 0.0 0.75 0.0
输出:
3 7.50 2 5.00 1 3.00
示例2
输入:
3 4 0 3 50 3 6 50 0 6 75 0.2 0.3 0.6 0.6 0.6 0.5 0.6 0.5 0.4 0.9 0.9 0.9
输出:
4 90.00 2 60.00 3 55.00
C++ 解法, 执行用时: 94ms, 内存消耗: 964K, 提交时间: 2022-02-10 10:56:00
#include<bits/stdc++.h>
using namespace std;
int t, p, s[12345], e, a[12345];
vector<int>q[12345];
pair<double, int>ans[12345];
int main()
{
cin >> t >> p;
for(int i = 0; i < t; i++)
{
cin >> s[i] >> e >> a[i];
q[e].push_back(i);
}
for(int i = 0; i < p; i++)
{
vector<double>pb(12345), g(12345);
for(int j = 0; j < t; j++)
cin >> pb[j];
for(int j = 0; j <= 10000; j++)
{
g[j] = g[j-!!j];
for(auto k : q[j])
g[j] = max(g[j], g[s[k]] + pb[k]*a[k]);
}
ans[i] = {g[10000], i+1};
}
sort(ans, ans+p);
for(int i = 1; i < 4; i++)
printf("%d %.2f\n", ans[p-i].second, ans[p-i].first);
}