Блог пользователя Z3R0_IQ

Автор Z3R0_IQ, история, 3 года назад, По-английски

Please anyone give me some hints for solving this. problem Link : Lightoj 1031: Easy Game

Alice and Bob are playing a two player game. Initially, there are n integer numbers in an array and Alice and Bob get chances to take them alternatively. Each player can take one or more numbers from the left-end or the right-end of the array but cannot take from both ends at one turn. A player can take as many consecutive numbers as he/she wants during his time. The game ends when all numbers are taken from the array.

The point of each player is calculated by the summation of the numbers, which the player has taken. Each player tries to achieve as much points as possible. If both Alice and Bob play optimally and Alice starts the game, then how much more point can Alice get than Bob?

Input Input starts with an integer T (≤ 100), denoting the number of test cases.

Each case contains a blank line and an integer N (1 ≤ N ≤ 100) denoting the size of the array. The next line contains N space separated integers. You may assume that no number will contain more than 4 digits.

Output For each test case, print the case number and the maximum difference Alice will be able to make after playing this game optimally.

Input 2 4 4 -10 -20 7 4 1 2 3 4

Output:

Case 1: 7 Case 2: 10

  • Проголосовать: нравится
  • -6
  • Проголосовать: не нравится

»
3 года назад, # |
Rev. 4   Проголосовать: нравится 0 Проголосовать: не нравится

There is a 2D dynamic programming solution for this problem in $$$O(N^2)$$$ time and space complexity as follows.

Initially, you can compute the prefix sum of the numbers in $$$O(N)$$$ time so that sum of the sub-array $$$A[l..r]$$$ can be computed for any $$$1 \leq l \leq r \leq N$$$ in $$$O(1)$$$ time. Then, let $$$DP[l][r]$$$ be the maximum difference that Alice will be able to make when playing the game optimally using the sub-array $$$A[l..r]$$$, i.e. it is the solution of the sub-problem $$$[l,r]$$$. The answer to the original problem is then equal to $$$DP[1][N]$$$.

The base case for $$$DP[l][r]$$$ is when $$$l = r$$$, and the answer is $$$dp[l][l] = A[l]$$$.

There are three different cases for the $$$A[l..r]$$$ sub-problem when $$$l < r$$$:

  1. Alice has taken the whole array, and the difference is $$$\sum\limits_{i~=~l}^{r} A[i]$$$.
  2. Alice has taken $$$k$$$ numbers from the left-end, where $$$1 \leq k \leq r-l$$$, and the difference is $$$( \sum\limits_{i~=~l}^{l+k-1} A[i] ) - DP[l+k][r]$$$.
  3. Alice has taken $$$k$$$ number from the right-end, where $$$1 \leq k \leq r-l$$$, and the difference is $$$( \sum\limits_{i~=~r-k+1}^{r} A[i] ) - DP[l][r-k]$$$.

The value of $$$DP[l][r]$$$ is then computed as the maximum value of these differences.

The following is my accepted C++ implementation of this solution.

C++