POJ 2738 - Two Ends

http://poj.org/problem?id=2738

概要

Two Ends という2人でプレイするカードゲームがある． 数字の書かれた n 枚のカードが一列に並べられており，プレイヤーは交互に両端のどちらかのカードを選んで取っていく． カードがなくなった時点で，自分の持っているカードの数字の合計が大きいほうが勝ち．

両端のうち数字の大きいほうを常に選ぶという貪欲な戦略が考えられるが，これが常に最適とは限らない． そこで，先手が自由な戦略をとり，後手が貪欲な戦略をとったときに，後手は最大で何点差で負けうるかを答える．

制約

解法

カードの状態は「i 番目から j 番目までが残っている」というものしかなく，高々 n^2 程度． この i, j に関してメモ化しながら再帰的に調べ上げた．

 1 #include <cstdio>
 2 #include <vector>
 3 using namespace std;
 4 
 5 int cache[1000][1000];
 6 bool is_cached[1000][1000];
 7 int solve(const vector<int>& v, int begin, int end)
 8 {
 9   if (begin > end) {
10     return 0;
11   } else if (is_cached[begin][end]) {
12     return cache[begin][end];
13   } else {
14     const int l = v[begin+1] >= v[end]
15       ? solve(v, begin+2, end) + v[begin] - v[begin+1]
16       : (solve(v, begin+1, end-1) + v[begin] - v[end]);
17     const int r = v[begin] >= v[end-1]
18       ? solve(v, begin+1, end-1) + v[end] - v[begin]
19       : (solve(v, begin, end-2) + v[end] - v[end-1]);
20     is_cached[begin][end] = true;
21     return cache[begin][end] = max(l, r);
22   }
23 }
24 
25 int main()
26 {
27   int T = 0;
28   int N;
29   while (scanf("%d", &N) != EOF && N != 0) {
30     vector<int> v(N);
31     for (int i = 0; i < N; i++) {
32       scanf("%d", &v[i]);
33     }
34     for (int i = 0; i < N; i++) {
35       fill_n(is_cached[i], N, false);
36     }
37     printf("In game %d, the greedy strategy might lose by as many as %d points.\n", ++T, solve(v, 0, N-1));
38   }
39   return 0;
40 }
poj/2738.cc