动态规划精解：CSP-J 2025真题《多边形》的背包问题解法

本题源自 CSP-J 2025 复赛，考察点聚焦于 动态规划 (Dynamic Programming) 和 背包问题 (Knapsack Problem) 的变体，并巧妙结合了多边形构成条件的几何性质。对于备考 GESP 六级或同等水平的选手而言，这是一道训练思维转化与算法优化能力的经典题目，洛谷难度标记为“普及/提高-”。

题目描述

小 R 有 n 根小木棍，第 i 根的长度为 a_i。
小 X 希望小 R 从中选出若干根，按任意顺序首尾相连拼成一个多边形。拼成多边形的条件是：对于选出的 k 根长度分别为 l_1, l_2, ..., l_k 的木棍，需满足 k ≥ 3 且所有木棍长度之和大于最长木棍长度的两倍，即 sum > 2 * max(l)。

问题是：有多少种选择木棍的方案（仅下标集合不同视为不同方案），使得选出的木棍能拼成一个多边形？答案对 998244353 取模。

输入格式

第一行一个正整数 n。
第二行 n 个正整数 a_i。

输出格式

一行一个非负整数，表示方案数取模后的结果。

输入输出样例 #1

输入 #1

5
1 2 3 4 5

输出 #1

9

输入输出样例 #2

输入 #2

5
2 2 3 8 10

输出 #2

6

题目分析与核心思路

1. 问题转化

多边形的关键条件是：总长度 > 2 * 最大长度。
若设选出的木棍中最大长度为 M，其余木棍长度之和为 S，则总长度为 S + M。条件变为：S + M > 2M，即 S > M。
因此，只要选定一个最大值 M，其余所选木棍的长度之和必须严格大于 M。

2. 枚举最大值的策略

为了有序地处理并避免重复，我们可以先将所有木棍从小到大排序。假设排序后数组为 a[1...n]。
当我们考虑第 i 根木棍 a[i] 作为选出的集合中的最大值时：

1. 我们只能从下标小于 i 的木棍中选取其他木棍（即更短或等长但先处理的木棍）。
2. 需要从前 i-1 根木棍中选若干根，使其长度之和 S > a[i]。
3. 一旦满足 S > a[i]，加上 a[i] 本身，就自动满足了 k ≥ 3 的条件（因为 S > a[i] 至少需要两根更短的木棍）。

3. 动态规划设计：补集转化

核心难点在于高效统计 S > a[i] 的方案数。直接计算“大于”较为困难，但计算其反面——“小于等于”——则简单得多。
对于固定的最大值 a[i]，不合法（即无法构成多边形）的条件是：S ≤ a[i]。
这个 S 的范围被限制在 [0, a[i]] 内，而 a[i] 最大为 5000，范围可控。

因此，我们的策略是：

1. 计算前 i-1 根木棍的所有子集总数（即 2^(i-1)）。
2. 计算不合法的方案数（即子集和 S ≤ a[i] 的方案数）。
3. 合法方案数 = 总方案数 - 不合法方案数。

4. DP 状态与转移

我们定义 dp[s]：在已处理的木棍中，选出若干根使其长度之和恰好为 s 的方案数。

• 初始状态：dp[0] = 1（空集），其余为 0。
• 状态转移：这本质上是一个 0/1 背包计数问题。当处理完当前最大值 a[i] 的贡献后，我们需要将 a[i] 加入“可选池”，以供后续更大的值作为“其他木棍”使用。转移方程为：
  新dp[j] = 旧dp[j] + 旧dp[j - a[i]] （j 从大到小遍历）
  • 旧dp[j]：不选 a[i] 的方案数。
  • 旧dp[j - a[i]]：选了 a[i]，则需要之前能凑出 j - a[i]。

关键：必须从大到小遍历 j，以确保 dp[j - a[i]] 是“上一轮”未包含 a[i] 的值，从而保证每根木棍只被使用一次。

5. 算法流程

1. 对木棍长度数组 a 进行排序。
2. 初始化 dp[0]=1, total_subsets=1（代表空集），答案 ans=0。
3. 遍历每根木棍 a[i]：
   a.  统计贡献：
   • 总子集数 = total_subsets。
   • 不合法方案数 = sum_{s=0}^{a[i]} dp[s]。
   • 合法贡献 = (total_subsets - 不合法方案数 + MOD) % MOD。
   • 将贡献累加到 ans。
     b.  更新 DP：将 a[i] 纳入背包，从大到小更新 dp 数组：for(j=MAX_VAL-1; j>=a[i]; j--) dp[j] = (dp[j] + dp[j-a[i]]) % MOD;
     c.  更新总子集数：total_subsets = (total_subsets * 2) % MOD; （因为对于之前的每个子集，现在都可选择是否加入 a[i]）
4. 输出 ans。

6. 复杂度分析

• 时间复杂度：O(n * max(a_i))，约为 2500万，可以接受。
• 空间复杂度：O(max(a_i))。

示例代码 (C++)

#include<algorithm>
#include<iostream>
#include<vector>

const int MOD = 998244353;
const int MAX_VAL = 5005;  // a_i 最大值是 5000

int dp[MAX_VAL];  // dp[s] 表示当前已处理的小木棍中，和为 s 的子集数量

int main() {
    // 优化 I/O
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    int n;
    std::cin >> n;

    std::vector<int> a(n);
    for (int i = 0; i < n; ++i) {
        std::cin >> a[i];
    }

    // 1. 排序：从小到大处理，保证处理 a[i] 时，它就是当前子集的最大值
    std::sort(a.begin(), a.end());

    // 初始化 DP
    // dp[0] = 1 (空集和为0)
    for (int i = 0; i < MAX_VAL; ++i) dp[i] = 0;
    dp[0] = 1;

    long long ans = 0;
    long long total_subsets = 1;  // 2^i, 初始也就是 2^0 = 1 (对应处理第一个元素之前)

    for (int i = 0; i < n; ++i) {
        int limit = a[i];

        // 2. 统计 “不合法” 的方案数
        // 所谓不合法，就是“除去最大边 a[i] 后，其余边之和 <= a[i]”。
        // 我们之前维护的 dp[s] 就是 sum=s 的方案数。
        // 所以我们把 s 从 0 到 a[i] 的所有 dp[s] 累加起来。
        long long invalid_count = 0;
        for (int s = 0; s <= limit; ++s) {
            invalid_count = (invalid_count + dp[s]) % MOD;
        }

        // 3. 计算以 a[i] 为最大边的贡献
        // 公式：贡献 = 总子集数 - 不合法数，注意处理负数取模
        long long contribution = (total_subsets - invalid_count + MOD) % MOD;
        ans = (ans + contribution) % MOD;

        // 4. 更新 DP 数组，加入 a[i] (0/1背包，从大到小更新)
        for (int j = MAX_VAL - 1; j >= limit; --j) {
            dp[j] = (dp[j] + dp[j - limit]) % MOD;
        }

        // 5. 更新总子集数 * 2
        total_subsets = (total_subsets * 2) % MOD;
    }

    std::cout << ans << std::endl;

    return 0;
}

关键细节与思考

• 为什么每一步都要取模？ 方案数可能极其庞大，远超 long long 的表示范围。步步取模可以防止溢出，且根据模运算的加法和乘法性质，最终结果与最后取模一致。
• 减法取模的坑：C++中 (a - b) % MOD 可能得到负数。正确写法是 (a - b + MOD) % MOD。
• 排序的重要性：排序确保了当我们处理 a[i] 时，它对于当前考虑的子集而言就是最大值，避免了复杂的状态去重。

解决此题需要对动态规划的模型转化（补集思想）和背包问题的计数更新（逆序枚举）有扎实的理解。理解透彻这道题，对于掌握竞赛中相关的组合计数与时间复杂度优化技巧大有裨益。对于算法竞赛和动态规划的更多深入探讨，欢迎在云栈社区交流分享。