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.


想了半天没什么思路~~大家帮偶想想,有什么思路~~~~

题目我大概翻译一下:
有2个人A,B做游戏,给出一组数,两个人轮流取数,要求,每次只能取第一个或者最后一个数.
A先取,然后B取,知道取完结束.B只会取第一个或者最后一个两者中的大的那一个.
用编程算法,计算出A最多能比B多出多少点数.
比如 3 2 10 4
A先取3,B只能取2和4中最大的,也就是取4,A取10,B取3,结果A比B多出3+10-(4+2)也就是7点.
输入:
首先输入一个数N,接下来有N个数组成的数组.当N=0时程序结束.
输出:
对于N个数组成的数组,A尽可能多的取得的比B多的最大点数;


输出格式就不翻译了,一看就明白的~~

意思就是都取最大的嘛~~

#include<Stdio.h>
main()
{
int i=0,j=9,a=0,b=0,si[10]={10,3,15,32,8,11,43,32,21};
while(1)
{if(si[i]>si[j])
{a+=si[i];i++;}
else
{a+=si[j];j--;}
if(si[i]>si[j])
{b+=si[i];i++;}
else
{b+=si[j];j--;}
if((j-i)<2) break;
}
printf("the greedy strategy might lose by as many as %d points",a-b);
}

[此贴子已经被作者于2006-12-9 23:50:45编辑过]

楼上的可能没分析清楚,B是一定取最大的,但是A不一定,就拿上面写的例子来说,
A先取,取的是3,那么B只能取4,A就能接着取到10,这样就很比B大7点.
如果A先取,去的是4的话,那么B接下来会去取10,结果是A输了.
题目要求我们寻找A取数的策略,使得A必须赢,而且需要赢最大的点数,也就是比B多出的点数最大.
对于B取的数,很简单就能实现,但是对于A怎么取数,就需要算法了.

我写了一个！不过是是wrong answer，测试数据都对了！
#include <stdio.h>
#define N 1000

int main()
{
int a[N], i = 1, j, sum1 = 0, t, s = 0, sum2 = 0, n;

while(scanf("%d", &n) != EOF&&n != 0)
{
for(j = 0;j < n;j ++)
scanf("%d", &a[j]);
t = n - 1;
for(j = 1;j <= n/2;j ++)
{
if(t - s == 1)
{
sum1 += a[s] > a[t] ? a[s] : a[t];
sum2 += a[s] > a[t] ? a[t] : a[s];
break;
}
if(a[t] < a[t - 1]&&a[t - 1] < a[t - 2]&&a[t - 2] > a[s])
{
sum1 += a[t];
t --;
}
else if(a[t] < a[t - 1]&&a[t - 1] >a[t - 2]&&a[t - 1] > a[s])
{
sum1 += a[s];
s ++;
}
else if(a[s] < a[s + 1]&&a[s + 1] >a[s + 2]&&a[s + 1] > a[t])
{
sum1 += a[s];
s ++;
}
else if(a[s] < a[s + 1]&&a[s + 1] < a[s + 2]&&a[s + 2] > a[t])
{
sum1 += a[s];
s ++;
}
else if(a[s] > a [t])
{
sum1 += a[s];
s ++;
}
else if(a[s] < a[t])
{
sum1 += a[t];
t --;
}
if(a[s] > a[t])
{
sum2 += a[s];
s ++;
}
else if(a[s] < a[t])
{
sum2 += a[t];
t --;
}

}
printf("In game %d, the greedy strategy might lose by as many as %d points.\n", i, sum1 - sum2);
sum1 = 0;
sum2 = 0;
i ++;
s = 0;
}

return 0;
}

[此贴子已经被作者于2006-12-10 11:05:06编辑过]

动态规划

楼上的可以说一下动态规划的思想吗？谢谢了！

6楼的解答只考虑了2层数据,有些情况不单但是考虑2曾就可以的,甚至有些情况需要整体分析所有数据.
用穷搜可能可以做出来,不过需要搜2^n/2数据太大了~~~

设f[i][j]为取i到j中的点数,A所能赢得的最大点数,则所求的答案就是f[1][n];
考虑到有偶数个点数时是A取,有奇数个点数时是B取.
f[i][i]=-a[i];i=1...n;
当j-i==奇数,A取
f[i][j]=max(f[i+1][j]+a[i],f[i][j-1]+a[j]);
当j-i==偶数,B取
如果a[i]>=a[j];
f[i][j]=f[i+1][j]-a[i];
否则f[i][j]=f[i][j-1]-a[j];