• Consider the following game. A “dealer” produces a sequence $s_1, …, s_n$ of “cards”, face up, where each card $s_i$ has a value $v_i$. Then two players take turns picking a card from the sequence, but can only pick the first or the last card of the (remaining) sequence. The goal is to collect cards of largest total value. (For example, you can think of the cards as bills of different denominations.) Assume n is even.

　(a) Show a sequence of cards such that it is not optimal for the first player to start by picking up the available card of larger value. That is, the natural greedy strategy is suboptimal.
　(b) Give an $O(n^2)$ algorithm to compute an optimal strategy for the first player. Given the initial sequence, your algorithm should precompute in $O(n^2)$ time some information, and then the first player should be able to make each move optimally in $O(1)$ time by looking up the precomputed information.

• 考虑如下博弈：发牌手准备了一摞扑克牌 $s_1, …, s_n$。从牌面上看，牌 $s_i$ 的价值为 $v_i$。现在两个玩家轮流拿牌，每人每次只能拿最前或最后的一张。玩家的目标是使所拿到的牌总价值最高（不妨想象这些牌都是有面值的筹码）。假设 $n$ 为偶数。
  • 请给出一个序列，使得先开始的玩家如果采取贪心策略（即每次取走能拿的牌中面值较大的一张），最终的牌总价值并不比另一个玩家大。

• 1 2 3 4 5

  Solution：{1, 2, 10, 3} 先手：3 后手：10（先手由于贪心损失最大牌值的一张牌） 先手：2 后手：1

  • 给出一个 $O(n^2)$ 的算法，用于计算先开始玩家的最优策略。给定初始序列，该算法首先利用 $O(n^2)$ 的时间进行预先计算，然后在每次选择时，玩家只需通过查找预先计算的结果即可在 $O(1)$ 内做出最有选择。
    Solution：
    　　$r(i, j)$ 表示在子串 $s[i, j]$ 中进行游戏时所获得的最大分数值（假设对手也总是采取最优的策略），设 $r_i$ 是在子串 $s[i, j]$ 中进行游戏时，先手第一步选择最前一张牌所能得到的分数； $r_j$ 是先手第一步选择最后一张牌所能得到的分数，则有：
    　　$\begin{cases}
    r_i = v_i + min(r(i+2, j), r(i+1, j-1))\cr
    r_j = v_j + min(r(i+1, j-1), r(i, j-2))
    \end{cases}$，当先手第一步选择最前一张牌后，在第二步的选择中，$r(i+2, j)$ 对应后手第一步选择剩下的最前一张牌，$r(i+1, j-1)$则是后手第一步选择剩下的牌中的最后一张；类似地，当先手第一步选择最后一张牌后，在第二步的选择中，$r(i+1, j-1)$ 对应后手第一步选择剩下的最前一张牌，$r(i, j-2)$则是后手第一步选择了最后一张牌。
    　　子串的长度 len 从2, 4, …, 初始序列长度 LEN，然后遍历（$i = 0,1,…,LEN-len-1: s[i, i+len]$）所有可能的子串进行如上的预处理。
    　　为了在 $O(1)$ 内做出最有选择，还需要记录对于每个子串，先手玩家第一步的选择 $c(i, j)：$
    　　$\begin{cases}
    if(r_i \gt r_j): c(i, j)=pickfront \cr
    else: \qquad c(i, j)=pickback
    \end{cases}$