呵呵 居然有人問我題目啊~ 倍感榮幸！~
?這可是我人生中的第一次！~
不能辜負了人家的期望呀，拼命也要做做-_-|||
題目:
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次的的一個回合內(nèi)），偶WA了一次貪心。但是WA后，發(fā)現(xiàn)貪心出不了最優(yōu)解（因為可能會有多組相同的解).
搜索顯然不行 ,1000的長度 + multiple test case => absolutely TLE.
于是考慮DP.
是否滿足最優(yōu)子結(jié)構(gòu)？恩。因為全局最優(yōu)解包含局部最優(yōu)解.
是否滿足無后效性? 恩。當前所作決策可由當前狀態(tài)唯一確定.
OK.DP.
首先是狀態(tài).不用說，用d[i][j]表示當前i->j的最大可能值(即2號選手少的分）
接著是狀態(tài)轉(zhuǎn)移.d[i][j]可能是兩個方向轉(zhuǎn)過來的，即選了最前面一個或最后面一個.然后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;
}
//代碼寫的不好 將就著看吧
呵呵 總算沒辜負人家期望啊~ 好開心~