Skip to content

14146: 【原4146】切数列

题目

题目描述

author: Yifan 原OJ链接:https://acm.sjtu.edu.cn/OnlineJudge-old/problem/4146

Description

有一个长度为n的正整数数列,其中奇数个数与偶数个数相等。你可以将这个数列切成若干段,但要求每一段中的奇数个数和偶数个数相等。如果在x和y中间将数列切断(x和y在数列中相邻),需要花费|x - y|枚金币。现在你有B枚金币,请问最多能切几次数列?

Input Format

第一行是n和B,2 <= n <= 100,1 <= B <= 100。

第二行是长度为n的正整数数列a1,a2,...,an(1 <= ai <= 100),其中奇数个数和偶数个数相等。

Output Format

输出一个整数,表示至多花费B枚金币的条件下最多能切几次数列。

Sample1 Input

6 4
1 2 5 10 15 20

Sample1 Output

1

Sample2 Input

6 100
1 2 3 4 5 6

Sample2 Output

2

Note

第一个样例切数列方案是1 2 | 5 10 15 20,花费|2 - 5| = 3枚金币。

第二个样例切数列方案是1 2 | 3 4 | 5 6,花费|2 - 3| + |4 - 5| = 2枚金币。

Oops! 本题目还没有解答!

助教老师们编题的速度,已经超过了解题的速度!

OJ翻了一新,但本解答集还大多用的是2017-2019级,甚至更早的同学们贡献的答案。

如果你已经AC了,可以的话,请您参考添加页面,与大家一起分享你的题解!