解题思路

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

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

• 初始：dp[i][1] = 1（只选 a[i] 这个长度为 1 的子序列）。
• 转移：当 j ≥ 2 时 dp[i][j] = Σ dp[t][j-1]，其中 0 ≤ t < i 且 a[t] * a[i] < 0（相邻符号相反）。 也可以用预处理的符号 sgn[i] = +1 / -1 来判定 sgn[t] ≠ sgn[i]。

最终答案：ans = Σ dp[i][k]（对所有 i 求和）。

该划分把所有可行子序列严格分到“以 i 结尾”的不交叠集合中，既不重不漏。实现时按下标从小到大填表，保证转移只依赖于更小下标的状态。

复杂度分析

• 时间复杂度：三重循环（i、j、t<i）为 O(n^2 · k)。在 n ≤ 30、k ≤ n 的数据范围内非常轻松。
• 空间复杂度：状态表 O(n · k)。计数可使用 64 位整型（Java long / C++ long long），Python 自动大整数。

代码实现

Python

# 交替子序列计数（长度恰为 k） - Python 实现（ACM 风格）
# 读入与输出在主函数，核心逻辑在外部函数中

from typing import List

def count_alternating_subseq(a: List[int], k: int) -> int:
    n = len(a)
    # 计算符号：正数为 1，负数为 -1（题意保证 a[i] != 0）
    sgn = [1 if x > 0 else -1 for x in a]
    # dp[i][j] 表示以 i 结尾、长度为 j 的方案数
    dp = [[0] * (k + 1) for _ in range(n)]
    # 长度为 1 的初值
    for i in range(n):
        dp[i][1] = 1
    # 状态转移
    for i in range(n):
        for j in range(2, k + 1):
            total = 0
            # 从更小下标 t 转移过来，且符号必须相反
            for t in range(i):
                if sgn[t] != sgn[i]:
                    total += dp[t][j - 1]
            dp[i][j] = total
    # 汇总长度为 k 的所有结尾
    ans = sum(dp[i][k] for i in range(n))
    return ans

def main():
    import sys
    data = sys.stdin.read().strip().split()
    n, k = map(int, data[:2])
    a = list(map(int, data[2:2+n]))
    print(count_alternating_subseq(a, k))

if __name__ == "__main__":
    main()

Java

// 交替子序列计数（长度恰为 k） - Java 实现（ACM 风格）
// 读入与输出在主函数，核心逻辑在静态方法中，类名为 Main

import java.util.*;

public class Main {
    // 核心函数：返回长度恰为 k 的交替子序列数量
    static long countAlternatingSubseq(int[] a, int k) {
        int n = a.length;
        int[] sgn = new int[n]; // 符号：正为 1，负为 -1
        for (int i = 0; i < n; i++) sgn[i] = a[i] > 0 ? 1 : -1;

        long[][] dp = new long[n][k + 1];
        // 长度为 1 的初值
        for (int i = 0; i < n; i++) dp[i][1] = 1;

        // 状态转移
        for (int i = 0; i < n; i++) {
            for (int len = 2; len <= k; len++) {
                long total = 0L;
                for (int t = 0; t < i; t++) {
                    if (sgn[t] != sgn[i]) {
                        total += dp[t][len - 1];
                    }
                }
                dp[i][len] = total;
            }
        }

        long ans = 0L;
        for (int i = 0; i < n; i++) ans += dp[i][k];
        return ans;
    }

    public static void main(String[] args) {
        // 根据数据范围，普通 Scanner 足够
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt(), k = sc.nextInt();
        int[] a = new int[n];
        for (int i = 0; i < n; i++) a[i] = sc.nextInt();
        System.out.println(countAlternatingSubseq(a, k));
    }
}

C++

// 交替子序列计数（长度恰为 k） - C++ 实现（ACM 风格）
// 读入与输出在主函数，核心逻辑在独立函数里

#include <bits/stdc++.h>
using namespace std;

// 核心函数：返回长度恰为 k 的交替子序列数量
long long countAlternatingSubseq(const vector<int>& a, int k) {
    int n = (int)a.size();
    vector<int> sgn(n); // 符号：正为 1，负为 -1
    for (int i = 0; i < n; ++i) sgn[i] = (a[i] > 0 ? 1 : -1);

    vector<vector<long long>> dp(n, vector<long long>(k + 1, 0));
    // 长度为 1 的初值
    for (int i = 0; i < n; ++i) dp[i][1] = 1;

    // 状态转移
    for (int i = 0; i < n; ++i) {
        for (int len = 2; len <= k; ++len) {
            long long total = 0;
            for (int t = 0; t < i; ++t) {
                if (sgn[t] != sgn[i]) {
                    total += dp[t][len - 1];
                }
            }
            dp[i][len] = total;
        }
    }

    long long ans = 0;
    for (int i = 0; i < n; ++i) ans += dp[i][k];
    return ans;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, k;
    if (!(cin >> n >> k)) return 0;
    vector<int> a(n);
    for (int i = 0; i < n; ++i) cin >> a[i];
    cout << countAlternatingSubseq(a, k) << "\n";
    return 0;
}

题目描述

给定一个长度为 $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]$ 合法