斑的家

A. Dima and Continuous Line

題意： 在一條線上有很多個半圓形，半圓的兩端在線上，問是否有任意兩個半圓會相交。

題解：暴力去試兩兩半圓是否相交。

B. Dima and Text Messages

題意：給兩個字串S1 , S2 。問 LCS(S2,S1) == S1 。

題解： 用兩個指針 p1 , p2 。 p1 指向目前 在 S1 的位置 , p2 指向目前 在 S2 的位置。

對於 p1 目前指向的 character ，從 p2 一直往右找到相同的character ，如果找得到， p1 ++ 。然後一直

重複到 p1 指向 s1 的結尾。

如果最後 p1 能指向 S1 的結尾，return "yes", 不然 return "no"

C. Dima and Containers

題意： 有 stack, queue, deque，三個container 。給一排數字，

出現 none- zero ，就要放到其中一個container。 如果是 zero ，

那就將 stack , queue ,deque 釋出各一個元素，並將所取出的元素值

累加到 sum ，然後將stack,queue,deque 淨空。目怎麼操作，最後的 sum 才會最大。

題解： 如果目前的數字是 zero ，那麼就希望將 stack , queue, deque 中拿出最

大的數字。可以先 parse 整串數字。見以下範例：

9 1 2 3 4 0 5 6 7 0

先看到 1,2,3,4

接著看到 0 。將目前最大的三個數字分別放到3 個container 中。假設最大的放stack, 次大放queue ，最後放deque。

4-> stack, 3 ->queue , 2-> deque。

剩下的 1 就丟到 deque ，用pushBack，而真的在deque 中會用到的數字用pushFront

sum = 4 + 3 + 2

接著淨空container

然後在以上述同樣的方式處理 5 , 6 , 7 , 0

這題的重點在於如何處理用不到的數字。

D. Dima and Hares

題意：有很多兔子站在一排，牠們要吃東西，吃東西的時候會散發joy 指數。吃東西是有順序的。如果兔子i 吃東西的時候，它兩旁的兔子都

還沒吃，則散發 joy Ai ，如果其中一隻兔子有吃東西，散發 joy Bi 。如果兩旁都吃飽了，散發 Ci 。

問怎麼餵，sum of joy 最大。兔子 N < 3000。

題解： dp 。