Machine Programming

题面翻译

题目描述：

有一家公司有 $k$ 台机器，并且有 $n$ 个任务需要完成，对于每一个任务我们知道它的开始时间 $s_i$ 和持续时间 $t_i$ ,并且完成这个任务后这家公司可以获利 $c_i$ 。每一台机器都可以处理任何任务，但不能同时处理多个任务，在处理某个任务时也不能切换到其他任务（即当某个机器处理任务 $i$ 时，在 $s_i$ 至 $s_i+t_i-1$ 时间段内就只能处理这个任务）。你需要选择一些任务来完成，使得总利润最大。

输入格式：

第一行为两个整数 $n\ (1\le n\le 1000)$，$k\ (\le k\le50)$ 。$n$ 和 $k$ 分别代表任务数量和机器数量。

接下来 $n$ 行每行三个整数 $s_i,t_i,c_i$ $(1\le s_i,t_i\le10^9,1\le c_i\le10^6)$，含义如描述。

输出格式：

输出 $n$ 个数字 $x_{1},x_{2},...,x_{n}$，以空格相隔。数字 $x_i$ 为 $1$ 或 $0$ ，$1$ 代表选择任务 $i$，$0$ 代表不选择。 如果有多个选择方案，输出任何一个即可。

by lyh

题目描述

One remarkable day company "X" received $k$ machines. And they were not simple machines, they were mechanical programmers! This was the last unsuccessful step before switching to android programmers, but that's another story.

The company has now $n$ tasks, for each of them we know the start time of its execution $s_{i}$ , the duration of its execution $t_{i}$ , and the company profit from its completion $c_{i}$ . Any machine can perform any task, exactly one at a time. If a machine has started to perform the task, it is busy at all moments of time from $s_{i}$ to $s_{i}+t_{i}-1$ , inclusive, and it cannot switch to another task.

You are required to select a set of tasks which can be done with these $k$ machines, and which will bring the maximum total profit.

输入格式

The first line contains two integer numbers $n$ and $k$ ( $1<=n<=1000$ , $1<=k<=50$ ) — the numbers of tasks and machines, correspondingly.

The next $n$ lines contain space-separated groups of three integers $s_{i},t_{i},c_{i}$ ( $1<=s_{i},t_{i}<=10^{9}$ , $1<=c_{i}<=10^{6}$ ), $s_{i}$ is the time where they start executing the $i$ -th task, $t_{i}$ is the duration of the $i$ -th task and $c_{i}$ is the profit of its execution.

输出格式

Print $n$ integers $x_{1},x_{2},...,x_{n}$ . Number $x_{i}$ should equal $1$ , if task $i$ should be completed and otherwise it should equal $0$ .

If there are several optimal solutions, print any of them.

样例 #1

样例输入 #1

3 1
2 7 5
1 3 3
4 1 3

样例输出 #1

0 1 1

样例 #2

样例输入 #2

5 2
1 5 4
1 4 5
1 3 2
4 1 2
5 6 1

样例输出 #2

1 1 0 0 1

提示

In the first sample the tasks need to be executed at moments of time 2 ... 8, 1 ... 3 and 4 ... 4, correspondingly. The first task overlaps with the second and the third ones, so we can execute either task one (profit 5) or tasks two and three (profit 6).