TouchStone
  请登录后使用
登录 注册
 系统首页  练习题库  考试列表  判题结果  问题讨论与解答  统计信息与排名
  • 首页
  • 题库
  • P1890
  • 题目
  • P1890【基础】跳格子游戏
    限制 : 时间限制 : 10000 MS   空间限制 : 65536 KB
    问题描述

    Freda小的时候很喜欢玩跳格子游戏~
    一天,Freda在地上画了一排格子,准备开始玩“喵星跳格子”。
    “喵星跳格子”的规则如下:所有的格子排成一排,一共N个,每个格子上都有一个数字。每只小猫每步可以跨过任意多个格子。小猫如果是第奇数步到达的某个格子,那么它的得分就加上这个格子上的数字;相反,小猫如果是第偶数步到达的某个格子,那么它的得分就减去这个格子上的数字。当然,每只小猫每次都应该朝着一个方向走,即只能沿着第一个格子到第N个格子的方向走,而不能往回走。当然,小猫不一定非要经过第1个或者第N个格子>_<。
    Freda想让它的得分最大,请你帮它计算下,它最多能得到多少分呢?

    输入格式

    第一行一个整数N,表示格子的数目。
    接下来N行每行一个整数,按照从1到N的顺序表示每个格子上的数字。

    输出格式

    一行一个整数表示Freda最多能够得到多少分。

    样例输入

    8
    7
    2
    1
    8
    4
    3
    5
    6

    样例输出

    17

    提示

    样例解释:
    第一步跳到第1个格子,分数+7。
    第二步跳到第3个格子,分数-1。
    第三步跳到第4个格子,分数+8。
    第四步跳到第6个格子,分数-3。
    第五步跳到第8个格子,分数+6。
    总得分为+7-1+8-3+6=17.
    数据范围:
    1<=N<=150000
    1<=每个格子上的数字<=500


    来源  改编自USACO 2003 U S Open Orange