编程就+分(5期)! — 编程爱好者社区

主题：编程就+分(5期)!

Lovely哆啦 [专家分：1360] 发布于 2007-07-21 18:27:00

问题:　游戏
问题描述：
有n个正整数序列，两个游戏者先后从序列的两端取数，取数后该数字被去掉并将该数累加到本游戏者的得分中，最终得分多者为胜利者。
任　务　：假若你先取数，输出你和对手都进行最优先择的情况下每个人的最终得分。
输入格式：输入文件的第一行为一个正整数n（2 ≤ N ≤ 100），表示整数序列的大小。
　　　　　第二行以及以后的各行为空格分隔的n个正整数（大小为1-200）。
输出格式：你和对手的最终得分由空格分隔(你的得分在前)。
样例一
输入输出
6 4 7 2 9 5 2 18 11

本帖地址： http://bbs.pfan.cn/post/243526.html

回复列表（共2个回复）

沙发

bigchen [专家分：1940] 发布于 2007-07-22 09:23:00

var
  s1,s2,n,i:integer;
  a:array[1..100] of integer;
begin
  readln(n);
  for i:=1 to n do
    begin
      read(a[i]);
      if i mod 2=1 then s1:=s1+a[i];
      if i mod 2=0 then s2:=s2+a[i];
    end;
  if s1>s2 then writeln(s1,' ',s2) else writeln(s2,' ',s1);
end.

板凳

bigchen [专家分：1940] 发布于 2007-07-22 09:26:00

这个是分析：
A方取走偶位置的数后，剩下两端数都处于奇位置；反之，若A方取走奇位置的数后，剩下两端数都处于偶位置。即无论B方如何取法，A方即可以取走奇位置的所有数，亦可以取走偶位置的所有数。由此萌发出另一种有效的贪心策略：若能够让A方取走“数和较大的奇（或偶）位置上的所有数”，则A方必胜。这样，取数问题便对应于一个简单问题：让A方取奇偶位置中数和较大的一半数。设j为A取数的奇偶位置标志，则j=0表示偶位置数和较大，A取偶位置上的所有数；j=1表示奇位置数和较大，A取奇位置的所有数。

我来回复

您尚未登录，请登录后再回复。点此登录或注册

主题：编程就+分(5期)!

回复列表（共2个回复）

我来回复

程序员工具箱 new

代码片段

本版新帖

主题：编程就+分(5期)!

回复列表 （共2个回复）

我来回复

程序员工具箱 new

代码片段

本版新帖

回复列表（共2个回复）