2506: 油箱(语法周赛 Round 18（思维场）)

内存限制：256 MB 时间限制：1.000 S
评测方式：文本比较 命题人：
提交：11 解决：10

题目描述

33DAI 有 n 个能装柴油的油箱，从 1 到 n 编号。编号为 i 个油箱最多能装 a_i 升柴油。

33DAI 非常怪，他一共想要不超过 m 升柴油，并且他希望相邻两个油箱装的柴油升数的奇偶性不同。

请问他一共有多少种装油方案？

输入

第一行两个整数 n,m。

接下来一行 n 个整数，即 a_1\sim a_n。

输出

一行一个整数，表示方案数

样例输入 复制 

3 6
6 6 6

样例输出 复制 

20

提示

3 6
6 6 6 
20 
3 6
3 3 3 
14

样例解释

样例 1 有以下 20种方案：

0,1,0、2,1,0、4,1,0、0,3,0、2,3,0、0,5,0、1,0,1、3,0,1、5,0,1、1,2,1、3,2,1、1,4,1、0,1,2、2,1,2、0,3,2、1,0,3、3,0,3、1,2,3、0,1,4、1,0,5

样例 2 有以下 14 种方案：

0,1,0、2,1,0、0,3,0、2,3,0、1,0,1、3,0,1、1,2,1、3,2,1、0,1,2、2,1,2、0,3,2、1,0,3、3,0,3、1,2,3

数据规模与约定

对于 100\% 的数据，1\le n \le 6，0\le m\le 100，0\le a_i\le 8

  • 子任务 1（30 分）：保证 n=2。
  • 子任务 2（30 分）：保证 a_i=1。
  • 子任务 3（40 分）：没有特殊限制。

来源/分类

提交提交记录统计露一手!