周而进

旅行商(SALESMAN)

旅行商认定如何优化旅行路线是一个非常棘手的计算问题，所以他决定沿着线性的多瑙河开展他的业务。他有一条快船能够在瞬间沿着多瑙河把他从任意开始的位置带到任意目的地，但是这条船很费油。它逆流而上(驶向源头的方向)每米花费U元，顺流而下每米花费D元(驶离源头的方向）。

沿着多瑙河有N个展销会是旅行商所感兴趣的。每个展销会只持续一天。对于任意一个展销会X，旅行商知道：①展销日期是Tx(该日期是从旅行商买船之日算起过去的天数)，②展销地点是Lx(该地点用它与源头的距离表示，单位为米)，③参加该展销会能赚到的钱数是Mx元。旅行商开始和结束旅程的地点都是他位于多瑙河边的家S (用它与源头的距离表示，单位为米)。

请帮助旅行商选择他是否参加，如果参加应该以什么样的顺序参加哪些展销会才能在旅行结束时获得最多的总收益。旅行商的总收益定义为他参加的所有展销会的收益和，减去他在河上顺流和逆流航行的总花费。

注意：如果展销会A在展销会B之前举行并且旅行商要参加这两个展销会，旅行商必须先参加A，之后才能参加B(即他不能先参加B后参加A)。当两个展销会在同一天举行，他可以按任意顺序参加这两个展销会。旅行商在一天之内参加的展销会的数目没有限制，但是他不能参加同一个展销会两次并在一个展销会上获得两次收益。他可以经过他已经参加过的展销会而不再获得任何收益。

任务

写一个程序，给定所有展销会的日期、地点和收益，以及旅行商的家的位置和他旅行的花费，计算他在旅行结束时可能获得的最大的总收益。

数据规模

1≤N≤500,000 展销会的数目

1≤D≤U≤10 旅行每米的花费，逆流而上(U)和顺流而下(D)

1≤S≤500,001 旅行商的家的位置

1≤Tk≤500,000 展销会k举行的日期

1≤Lk≤500,001 展销会k的地点

1≤Mk≤4,000 旅行商参加展销会k所能获得的收益

输入

你的程序需要从标准输入读人下列数据：

· 第一行依次包含整数N，U，D和S，整数之间用空格隔开。

· 接下来的N行描述了N个展销会的情况(不按特定顺序)。这N行中的第kth行描述了第kth个展销会的情况，它包含三个整数(整数之间分别用一个空格隔开)分别表示展销会的日期Tk，地点Lk，和收益Mk。

注意：输人中给出的所有地点都是不同的。即没有两个展销会在同一个地点举行，也没有展销会在旅行商的家的位置上举行。

输出

你的程序必须向标准输出写入一行，该行包含一个整数：旅行商结束旅行时能够获得的最大总收益。

评分说明

有60分的评测数据，没有两个展销会在同一天举行。

有40分的评测数据，所有输人数据都不超过5,000。

有15分的评测数据同时满足上述两个条件。

有85分的评测数据满足上述两个条件中至少一个。

样例

输入样例

4 5 3 100

2 80 100

20 125 130

10 75 150

5 120 110

输出样例

50

解答

假设没有一个展销会在同一天举行，那么对于一个方案只需考虑参加哪些展销会而不用关心参加的顺序(因为必定是按照时间顺序参加的),下面我们就先考虑没有一个展销会在同一天的情况。

将所有的展销会按时间顺序排序，令Fi表示参加完第i个展销会后的最大获利，则

Fi = max { Fj-cost(j,i) | j<i }

Cost(i,j) = (Li - Lj )*U Li>=Lj

(Lj - Li )*D Li<Lj

这是一个O(N2)的算法，效率不高，需要进行优化。

这里可以发现，顺流和逆流只有在花费上不同，其他都一样，所以这里对于状态F[i]只考虑逆流的情况(也就是满足j<i且Lj<=Li)。可以发现，决策j优于决策k的情况是:

Fj - (Li - Li)*D > Fk - (Li - Lk)*D

Fj + Lj*D > Fk+ Lk*D

这是与i无关的，所以我们只需要对于状态i，查询L在区间[ 1..Li ]中F+L*D的最大值就可以了。这个操作可以用线段树完成，所以针对顺流和逆流都维护一个线段树，此问题就可以在O(NlogN)时间内完成。

最后考虑存在多个展销会在同一天完成的情况。由于在这一天之前和之后的情况都可以用前面的算法完成，所以只需要考虑这一天内选择参加哪些展销会并且如何安排行程。取出同一天的所有展销会，将展销会按L排序，可以发现，如果我参加展销会i和展销会j，满足Li<Lj,那么对于所有Li<Lk<Lj的展销会k我也必然参加。这个结论是显然的，因为我必定经过展销会k。有了这个结论我们就可以发现，选择参加的展销会必定是连续的一段区间，所以我必定最多只走连续的一趟顺流路线和逆流路线。这样提示我们还是可以用动态规划解决问题。

令fi表示参加展销会i且i之前的展销会不与i在同一天的最大获利，FUi表示对于与i同一天内的展销会只考虑逆流参加时的最大获利，对于FUi有转移：

FUi = max { fi , fi+1 + cost (i+1,i) }

因为这里只考虑了逆流，所以需要将顺流也考虑进去:

Fi = max {FUi , Fi-1 + cost (i-1,i) }

这样，处理一天的展销会的复杂度最多是O(N),因为一个展销会只被处理一次，所以总复杂度也是O(N),这个算法的复杂度就是O(NlogN)，可以解决此题。

POI

全部数据评测

普罗夫迪夫信息学奥赛的比赛规则与众不同。有N个参赛选手和T个题目，每个题目只有一个测试点，因此，对于每个参赛选手来说，他们的每个题目只可能有2种结果：解出或者没有解出，没有任何一个题目有部分得分。

每个题目的分值在比赛结束后才决定，分值等于没有解出该题目的所有选手的人数。每个选手的得分等于他们解出的题目的分值之和。

P hilip参加了比赛，但是他被复杂的计分规则搞晕了，看着比赛结果却无法知道自己最后的排名。

请你写一个程序帮助Philip计算他的得分和排名。

比赛之前，分配给每个选手一个唯一的ID(从1到N)。Philip的ID是P。比赛的最后排名按选手得分的降序排列，得分相同的情况下，解出题目多的选手排在解出题目少的选手之前，得分相同并且解出题目也相同的情况下，按照选手lD的升序排列。

任务

给定每个选手的解题情况，请你写程序计算Philip的得分以及他在最终排名中的名次。

数据规模

1≤N≤2,000 选手的人数

1≤T≤2,000 题目的数目

1≤P≤N Philip的ID

输入

你的程序需要从标准输入中读人下列数据：

第一行包含整数N，T和P，每两个整数之间用一个空格隔开。

接下来的N行描述了选手的解题情况，其中的第k行描述了ID为k的选手的解题情况。第k行包含T个整数，分别以空格隔开，其中第一个整数表示选手k是否解出了第一个题目，第二个整数表示选手k是否解出了第二个题目，依此类推。这T个整数均为0或者1，1表示选手k解出了相应的题目，而0表示选手k没有解出该题目。

输出

你的程序需要向标准输出写入一行，包含以空格隔开的2个整数。第一个整数表示Philip在POI比赛中的得分，第二个整数表示Philip在最终排名中的名次，该名次是一个1到N之间的整数，1表示排名最高(即该选手得到了最高分)，N表示排名最后(即选手的得分最低)。

评分规则

35分的测试数据中，没有人与Philip得分相同。

解答

这是IOI第一试中最简单的一个题，很容易解出。

首先计算每位选手的得分和做出题的个数，储存下每个题做出的人数就可以知道每道题的分值，从而也就知道了每位选手的得分。

最后对选手进行排序就可以了，按照得分、做出题目数、ID3个关键字排序即可。

复杂度O(NT)。