2014-2015 ACM-ICPC Northeastern European Regional Contest (NEERC 14)

Problem A

Solved by oxx1108. 0:15:12

题意：

题解：

Problem B

Solved by Xiejiadong. 0:58:32

题意：可以获得的快乐值是$\sum _{i=1}^{n} s_i*a_i$，不快乐值是$\sum _{i=1}^{n} s_i*b_i$，在保证不快乐值小于等于$B$的情况下最大化快乐值。

题解：按照$a_i/b_i$排序，便可以保证在$\sum b_i*s_i$小的情况下$\sum a_i*s_i$最大，贪心地把不快乐值填满即可。

Problem C

Unsolved.

题意：

题解：

Problem D

Unsolved.

题意：

题解：

Problem E

Unsolved.

题意：

题解：

Problem F

Solved by oxx1108. 1:34:38(-1)

题意：

题解：

Problem G

Unsolved.

题意：

题解：

Problem H

Unsolved.

题意：

题解：

Problem I

Solved by Xiejiadong. 1:56:32

题意：相邻的飞船之间有绳相连，第一个飞船与坐标为0的空间站相连，移动尽量少的飞船，使得绳子之间没有交叉。

题解：如果我们按照飞船的坐标排序形成飞船的编号数列，我们可以发现只需要对编号数列求一个单峰的最长子序列即可。

我们发现，所有不交叉的绳子都是在不断缩小的区间里面来回跳，那么我们做了单峰的最长子序列以后我们可以发现区间中的跳，变成了下午这样的跳：

alt text

顺着做一遍最长上生子序列，再到这做一遍最长上生子序列，暴力美女拼起来即可。

Problem J

Solved by oxx1108. 0:46:31

题意：

题解：

Problem K

Solved by dreamcloud. 0:23:11

题意：

题解：