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.
题意：给定一个数列，两人轮流取数，只能从两端取，第一个取的人可以用任何策略，第二个贪心，问结束时第一个人会赢多少分。
思路就是Top-Down的动态规划+记忆化搜索或者Bottom-Up的动态规划,，复杂度O(n2)。由于有比较多的判断就不写状态转移方程了，具体见代码和注释。
Notes:
Top-Down DP + Memorization 与 Bottom-Up DP 的区别
两种写法：
1. Top-Down：
//#define JDEBUG #include<cstdio>
#include<cstring>
#include<algorithm> int cards[];
int state[][]; /**
* Top-Down DP. Get the scores won by a in [l, r]
*
* @param l start of the interval
* @param r end of the interval
* @return the scores won by a in [l, r]
*/
int dp(int l, int r) {
// reach the end
if (l > r)
return ;
// one card
if (l == r)
return cards[l];
// [Memoization] searched
if (state[l][r] != -)
return state[l][r]; int takeLeft = , takeRight = ; // check what happens if a takes left
// cards[r] > cards[l+1], so b would take right
// narrowdown to [l+1, r-1]
if (cards[r] > cards[l + ]) {
takeLeft = dp(l + , r - ) + cards[l];
} else { // cards[r] <= cards[l+1], so b would take next left
// narrow down to [l+2, r]
takeLeft = dp(l + , r) + cards[l];
} // check what happens if a takes right
// cards[r-1] > cards[l], so b would take next right
// narrow down to [l, r-2]
if (cards[r - ] > cards[l]) {
takeRight = dp(l, r - ) + cards[r];
} else { // cards[r-1] <= cards[l], so b would take left
// narrow down to [l+1, r-1]
takeRight = dp(l + , r - ) + cards[r];
} // return the best outcome
return state[l][r] = (takeLeft > takeRight) ? takeLeft : takeRight;
} int main(void) {
#ifdef JDEBUG
freopen("1176.in", "r", stdin);
freopen("1176.out", "w", stdout);
#endif int n = ;
int game = ;
while(scanf("%d", &n) && n != ) {
// initialization
int sum = ;
memset(cards, -, sizeof(cards));
memset(state, -, sizeof(state)); for(int i = ; i < n; i++) {
scanf("%d", &cards[i]);
sum += cards[i];
} int scoreOfA = dp(, n - );
int scoreOfB = sum - scoreOfA;
printf("In game %d, the greedy strategy might lose by as many as %d points.\n",
game++, scoreOfA - scoreOfB);
}
}
2. Bottom-Up
//#define JDEBUG
#include<cstdio>
#include<cstdlib>
#include<cstring> int cards[];
int state[][]; /**
* Bottom up DP.
*
* @param n number of cards
* @return score by which b will lose
*/
int dp(int n) {
// base case: in [i, i+1], a would take the larger one,
// so b lose by abs(cards[i] - cards[i + 1])
for (int i = ; i < n - ; i++) {
state[i][i + ] = abs(cards[i] - cards[i + ]);
} // dp starts from [l, l+3] since [l, l+1] is known
// iterate: when [l, l+intvl] are left
for (int intvl = ; intvl < n; intvl++) {
for (int l = ; l < n - intvl; l++) {
int r = l + intvl;
int takeLeft = , takeRight = ; // check what happens if a takes left
// cards[r] > cards[l+1], so b would take right
if (cards[r] > cards[l + ]) {
takeLeft = state[l + ][r - ] + cards[l] - cards[r];
} else { // cards[r] <= cards[l+1], so b would take next left
takeLeft = state[l + ][r] + cards[l] - cards[l + ];
} // check what happens if a takes right
// cards[r-1] > cards[l], so b would take next right
if (cards[r - ] > cards[l]) {
takeRight = state[l][r - ] + cards[r] - cards[r - ];
} else { // cards[r-1] <= cards[l], so b would take left
takeRight = state[l + ][r - ] + cards[r] - cards[l];
} // use the one with the best outcome
state[l][r] = takeLeft > takeRight ? takeLeft : takeRight;
}
} return state[][n - ];
} int main(void) {
#ifdef JDEBUG
freopen("1176.in", "r", stdin);
freopen("1176.out", "w", stdout);
#endif
int n = ;
int game = ; while (scanf("%d", &n) && n != ) {
// store the card numbers
for (int i = ; i < n; i++) {
scanf("%d", &cards[i]);
} memset(state, , sizeof(state));
printf("In game %d, the greedy strategy might lose by as many as %d points.\n",
game++, dp(n));
} return ;
}