解题思路
本题属于典型的“划分型动态规划”。将所有满足条件的子序列按其“最后一个元素所在位置”进行划分：对每个位置 i，统计所有以 a[i] 作为末尾元素且长度为 j 的交替子序列数量，最后把长度为 k 的各部分相加即为答案。
设
dp[i][j] = 以位置 i 结尾、长度恰为 j 的交替子序列数量。
则有：
- 初始：
dp[i][1] = 1（只选 a[i] 这个长度为 1 的子序列）。
P3863.组合问题(四):k-交替子序列
题目描述
给定一个长度为 n 的整数数组 a=[a1,a2,…,an]，统计从中选出长度恰为 k 的交替子序列的方案数。
定义
- 子序列：从数组中选出若干下标 1≤i1<i2<⋯<ik≤n，形成序列 [ai1,ai2,…,aik]。
- 交替（符号相反）：对任意相邻对 (ai,aii+1) 都满足ai∗ai+1<0。即相邻元素的符号严格相反。
输入格式
- 第一行包含两个整数 n,k。
- 第二行包含 n 个整数 a1,a2,…,an。
输出格式
输出一个整数，表示满足条件的长度为 k 的交替子序列的方案数。
数据范围
- 1≤n≤30
- 1≤k≤n
- −100≤ai≤100且ai=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] 合法
开通会员即可查看完整视频题解： 1.题目讲解 2.思路分析 3.逐行代码手写
