解题思路

本题属于典型的“划分型动态规划”。将所有满足条件的子序列按其“最后一个元素所在位置”进行划分：对每个位置 i，统计所有以 a[i] 作为末尾元素且长度为 j 的交替子序列数量，最后把长度为 k 的各部分相加即为答案。

设 dp[i][j] = 以位置 i 结尾、长度恰为 j 的交替子序列数量。 则有：

• 初始：dp[i][1] = 1（只选 a[i] 这个长度为 1 的子序列）。

题目描述

给定一个长度为 $n$ 的整数数组 $a=[a_1,a_2,\ldots,a_n]$，统计从中选出长度恰为 $k$ 的交替子序列的方案数。

定义

• 子序列：从数组中选出若干下标 $1 \le i_1 < i_2 < \cdots < i_k \le n$，形成序列 $[a_{i_1},a_{i_2},\ldots,a_{i_k}]$。
• 交替（符号相反）：对任意相邻对 $(a_{i},a_{i_{i+1}})$ 都满足$a_i * a_{i+1} < 0$。即相邻元素的符号严格相反。

输入格式

• 第一行包含两个整数 $n,k$。
• 第二行包含 $n$ 个整数 $a_1,a_2,\ldots,a_n$。

输出格式

输出一个整数，表示满足条件的长度为 $k$ 的交替子序列的方案数。

数据范围

• $1 \le n \le 30$
• $1 \le k \le n$
• $-100 \le a_i \le 100 且 a_i \neq 0$

样例 1

输入

5 3
3 -1 2 -2 4

输出

5

说明 满足条件的长度为 $3$ 的交替子序列共有 $5$ 个： $[3,-1,2]$, $[3,-1,4]$, $[3,-2,4]$, $[-1,2,-2]$, $[2,-2,4]$。

样例 2

输入

3 2
1 1 -1

输出

2

说明 长度为 $2$ 的交替子序列必须相邻乘积 $<0$。 有两个 $[1,-1]$ 合法