sicily_1176 Two Ends

题目

Constraints

Time Limit: 1 secs, Memory Limit: 64 MB

Description

In the two-player game "Two Ends", an even number of cards is laid out in a row. On each card, face up, is written a positive integer. Players take turns removing a card from either end of the row and placing the card in their pile. The player whose cards add up to the highest number wins the game. Now one strategy is to simply pick the card at the end that is the largest -- we'll call this the greedy strategy. However, this is not always optimal, as the following example shows: (The first player would win if she would first pick the 3 instead of the 4.)
3 2 10 4
You are to determine exactly how bad the greedy strategy is for different games when the second player uses it but the first player is free to use any strategy she wishes.

Input

There will be multiple test cases. Each test case will be contained on one line. Each line will start with an even integer n followed by n positive integers. A value of n = 0 indicates end of input. You may assume that n is no more than 1000. Furthermore, you may assume that the sum of the numbers in the list does not exceed 1,000,000.

Output

For each test case you should print one line of output of the form:
In game m, the greedy strategy might lose by as many as p points.
where m is the number of the game (starting at game 1) and p is the maximum possible difference between the first player's score and second player's score when the second player uses the greedy strategy. When employing the greedy strategy, always take the larger end. If there is a tie, remove the left end.

Sample Input

4 3 2 10 4
8 1 2 3 4 5 6 7 8
8 2 2 1 5 3 8 7 3
0

Sample Output

In game 1, the greedy strategy might lose by as many as 7 points.
In game 2, the greedy strategy might lose by as many as 4 points.
In game 3, the greedy strategy might lose by as many as 5 points.

思路

目标是在后手总是使用贪心策略的情况下，让先手赢，并且计算赢了多少分数。也就是说，先手每一步都要取得最优策略，需要用到动态规划。
而动态规划也有Top-Down DP+记忆化搜索和bottom-up DP两种思路，本文使用的是第一种（引入每个过程的最优取法的结果）

代码

// Copyright (c) 2015 HuangJunjie@SYSU(SNO:13331087). All Rights Reserved.
// sicily_1176 Two Ends: http://soj.sysu.edu.cn/1176
#include <cstdio>
#include <cstring>

#define MAX_SIZE 1000

// global variables.
int cards[MAX_SIZE + 1];  // abandons cards[0].

// two dimension array used to record the best strategy answer in part of the
// sequence.
int states[MAX_SIZE + 1][MAX_SIZE + 1];


// Top-down DP refering http://www.cnblogs.com/joyeecheung/p/3995682.html.
// considers your opposite are the second guy and always use the Greedy 
// stratege, but the you want to win him, so you should find the best way 
// to win him.
//
// @Param left: the left card remains
// @Param right: the right crad remains
// @return: the score that you can win.
int dp(int left, int right) {
  // the final cards is taken away by your opposite
  if (left > right) return 0;

  // only the final card you can choose.
  if (left == right) return cards[left];

  // if the best strategy has not been analyzed, analyzed it.
  // you are A, your opposite is B.
  if (states[left][right] == -1) {
    // considers taking either side's card
    int takeLeft = 0, takeRight = 0;

    // if the left side is taken, which will B take.
    // here has a question that two different operator '>' and '>=' will cause
    // difference answers. The reson why is still being cosidered
    if (cards[right] > cards[left+1]) {
      takeLeft = dp(left + 1, right - 1) + cards[left];
    } else {
      takeLeft = dp(left + 2, right) + cards[left];
    }

    // if the right side is taken, which will B take.
    // here has a question that two different operator '>' and '>=' will cause
    // difference answers. The reson why is still being cosidered
    if (cards[left] >= cards[right-1]) {
      takeRight = dp(left + 1, right - 1) + cards[right];
    } else {
      takeRight = dp(left, right-2) + cards[right];
    }

    // get the better strategy.
    states[left][right] = takeLeft > takeRight ? takeLeft : takeRight;
  }

  return states[left][right];
}
int main() {
  int n;
  for (int game = 1; scanf("%d", &n) != EOF && n; game++) {
    // reset the global variables to avoid miscalculation.
    memset(cards, -1, sizeof(cards));
    memset(states, -1, sizeof(states));
    int sum = 0;
    for (int i = 1; i <= n; i++) {
      scanf("%d", &cards[i]);
      sum += cards[i];
    }

    int sumA = dp(1, n);
    int sumB = sum - sumA;
    printf("In game %d, the greedy strategy might lose by as many as %d points.\n",
           game, sumA - sumB);
  }
  return 0;
}

参考

http://www.cnblogs.com/joyeecheung/p/3995682.html