logo AlgoBeat OnlineJudge
登录 注册

#101915. [BZOJ 1915] [Usaco2010 Open]奶牛的跳格子游戏

内存限制:64 MiB 时间限制:4000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: 匿名

题目描述

奶牛们正在回味童年,玩一个类似跳格子的游戏,在这个游戏里,奶牛们在草地上画了一行N个格子,(3

一个合法的序列Bessie可以选择的是0[0], 1[0], 3[2], 2[1], 0[0]。(括号里的数表示钱数)

这样,可以得到的钱数为0+0+2+1+0 = 3。 如果Bessie选择一个序列开头为0, 1, 2, 3, ...,那么她就没办法跳回去了,因为她没办法再跳到一个之前没跳过的格子。序列0[0], 2[1], 4[-3], 5[4], 3[2], 1[0], 0[0]是最大化钱数的序列之一,最后的钱数为(0+1-3+4+2+0 = 4)。

输入格式

  • 第1行 1: 两个用空格隔开的整数: N 和 K
  • 第2到N+1行: 第i+1行有一个整数: V_i

输出格式

  • 第一行: 一个单个的整数表示最大的钱数是多少。

样例

样例输入

5 2
0
1
2
-3
4

样例输出

4

OUTPUT DETAILS:

还有一种可能的最大化钱数的序列是: 0 2 4 5 3 1 0