呵呵 居然有人问我题目啊~ 倍感荣幸！~
这可是我人生中的第一次！~
不能辜负了人家的期望呀，拼命也要做做-_-|||
题目:
PKU 2738
Two Ends
Time Limit:1000MS Memory Limit:65536K
Total Submit:605 Accepted:262
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.
Source
East Central North America 2005
思维:
看到这题首先分析情形。初看似乎可以贪心（即每人2次的的一个回合内），偶WA了一次贪心。但是WA后，发现贪心出不了最优解（因为可能会有多组相同的解).
搜索显然不行 ,1000的长度 + multiple test case => absolutely TLE.
于是考虑DP.
是否满足最优子结构？恩。因为全局最优解包含局部最优解.
是否满足无后效性? 恩。当前所作决策可由当前状态唯一确定.
OK.DP.
首先是状态.不用说，用d[i][j]表示当前i->j的最大可能值(即2号选手少的分）
接着是状态转移.d[i][j]可能是两个方向转过来的，即选了最前面一个或最后面一个.然后2nd player也应该会有一个相应的选择.(具体见程序)
做好初始化的工作,就OK啦
Solution:
#include <stdio.h>
#include <string.h>
#include <math.h>
int a[1010], n, d[1010][1010];
int SecondDecision(int i, int j) //return which the Second player would like to get
{
if(a[i] >= a[j]) return i;
return j;
}
int Cal() //Dynamic Programming
{
int l, i, j, temp = 0;
for(i=1; i<n; i++)
d[i][i+1] = abs(a[i] - a[i+1]);
for(l = 4; l <= n; l += 2) //case length=2 has been calculated
for(i=1; i<=n-l+1; i++)
{
j = i+l-1;
if(SecondDecision(i+1, j) == j && d[i+1][j-1] >= 0)
{
temp = d[i+1][j-1] + a[i] - a[j];
d[i][j] = temp > d[i][j] ? temp : d[i][j];
}
else if(d[i+2][j] >= 0)
{
temp = d[i+2][j] + a[i] - a[i+1];
d[i][j] = temp > d[i][j] ? temp : d[i][j];
}
if(SecondDecision(i, j-1) == j-1 && d[i][j-2] >= 0)
{
temp = d[i][j-2] + a[j] - a[j-1];
d[i][j] = temp > d[i][j] ? temp : d[i][j];
}
else if(d[i+1][j-1] >= 0)
{
temp = d[i+1][j-1] + a[j] - a[i];
d[i][j] = temp > d[i][j] ? temp : d[i][j];
}
}
return d[1][n];
}
int main()
{
// freopen("ends.in", "r", stdin);
int i, ntc = 0;
while(scanf("%d", &n), n>0)
{
ntc++;
memset(a, 0, sizeof(a));
memset(d, -1, sizeof(d));
for(i=1; i<=n; i++)
scanf("%d", &a[i]);
printf("In game %d, the greedy strategy might lose by as many as %d points.\n", ntc, Cal());
}
return 0;
}
//代码写的不好 将就着看吧
呵呵 总算没辜负人家期望啊~ 好开心~