简单背包与区间类型动态规划

简单背包类型动态规划；简单区间类型动态规划。

概念

背包型 DP：dp[i][w] 或滚动数组表示「前 i 个物品、容量/限制 w 下能否达到/最优值」，每件物品常对应选或不选（0-1 背包）或有限次数。区间型 DP：在 [l,r] 区间上合并或决策，dp[l][r] 由更短子区间转移而来（如合并石子、回文划分等 CSP-J 简化版）。本叶子比 cspj.algo.dp-basic 多一维约束（容量、重量、区间端点），转移里要带「选物品」或「切分点 k」。CSP-J 复赛可能把背包思想藏在「选若干数满足和/长度约束」的建模里，而不出现经典物品名称。

CSP-J 常考

目前语料只有 1 道：

cspj-r2-2025 第 4 题：复赛编程，固定最大值后用背包型 DP 统计满足拼多边形条件的子集。

// 0-1 背包：n 个物品，容量 W，dp[w]=能否凑出重量 w
bool dp[1001] = {true};
for (int i = 0; i < n; ++i)
    for (int w = W; w >= weight[i]; --w)
        dp[w] = dp[w] || dp[w - weight[i]];
// 内层 w 倒序保证每件只用一次

易错点

0-1 背包正序遍历 w 导致同一物品用多次，与完全背包方向搞反。
区间 DP 枚举切分点 k 时边界 l..k 与 k+1..r 写错，完善程序空位常考 k 的起止。
状态含义混淆：是「恰好装满」还是「不超过」，初值 dp[0]=true/false 要跟着定义走。

编程题

多边形

C++时间 1 s内存 512 MB 文件 IO：polygon.in → polygon.out

小 R 喜欢玩小木棍。小 R 有 $n$ 根小木棍，第 $i$ $(1 \le i \le n)$ 根小木棍的长度为 $a_i$ 。

小 X 希望小 R 从这 $n$ 根小木棍中选出若干根小木棍，将它们按任意顺序首尾相连拼成一个多边形。小 R 并不知道小木棍能拼成多边形的条件，于是小 X 直接将条件告诉了他：对于长度分别为 $l_1, l_2, \ldots, l_m$ 的 $m$ 根小木棍，这 $m$ 根小木棍能拼成一个多边形当且仅当 $m \ge 3$ 且所有小木棍的长度之和大于所有小木棍的长度最大值的两倍，即 $\sum_{i=1}^{m} l_i > 2 \times \max_{i=1}^{m} l_i$ 。

由于小 R 知道了小木棍能拼成多边形的条件，小 X 提出了一个更难的问题：有多少种选择小木棍的方案，使得选出的小木棍能够拼成一个多边形？你需要帮助小 R 求出选出的小木棍能够拼成一个多边形的方案数。两种方案不同当且仅当选择的小木棍的下标集合不同，即存在 $1 \le i \le n$ ，使得其中一种方案选择了第 $i$ 根小木棍，但另一种方案未选择。由于答案可能较大，你只需要求出答案对 $998,244,353$ 取模后的结果。

输入格式

从文件 polygon.in 中读入数据。

输入的第一行包含一个正整数 $n$ ，表示小 R 的小木棍的数量。

输入的第二行包含 $n$ 个正整数 $a_1, a_2, \ldots, a_n$ ，表示小 R 的小木棍的长度。

输出格式

输出到文件 polygon.out 中。

输出一行一个非负整数，表示小 R 选出的小木棍能够拼成一个多边形的方案数对 $998,244,353$ 取模后的结果。

样例

输入 1

5
1 2 3 4 5

输出 1

共有以下 $9$ 种选择小木棍的方案，使得选出的小木棍能够拼成一个多边形：

选择第 $2, 3, 4$ 根小木棍，长度之和为 $2 + 3 + 4 = 9$ ，长度最大值为 $4$ ；
选择第 $2, 4, 5$ 根小木棍，长度之和为 $2 + 4 + 5 = 11$ ，长度最大值为 $5$ ；
选择第 $3, 4, 5$ 根小木棍，长度之和为 $3 + 4 + 5 = 12$ ，长度最大值为 $5$ ；
选择第 $1, 2, 3, 4$ 根小木棍，长度之和为 $1 + 2 + 3 + 4 = 10$ ，长度最大值为 $4$ ；
选择第 $1, 2, 3, 5$ 根小木棍，长度之和为 $1 + 2 + 3 + 5 = 11$ ，长度最大值为 $5$ ；
选择第 $1, 2, 4, 5$ 根小木棍，长度之和为 $1 + 2 + 4 + 5 = 12$ ，长度最大值为 $5$ ；
选择第 $1, 3, 4, 5$ 根小木棍，长度之和为 $1 + 3 + 4 + 5 = 13$ ，长度最大值为 $5$ ；
选择第 $2, 3, 4, 5$ 根小木棍，长度之和为 $2 + 3 + 4 + 5 = 14$ ，长度最大值为 $5$ ；
选择第 $1, 2, 3, 4, 5$ 根小木棍，长度之和为 $1 + 2 + 3 + 4 + 5 = 15$ ，长度最大值为 $5$ 。

输入 2

5
2 2 3 8 10

输出 2

共有以下 $6$ 种选择小木棍的方案，使得选出的小木棍能够拼成一个多边形：

选择第 $1, 2, 3$ 根小木棍，长度之和为 $2 + 2 + 3 = 7$ ，长度最大值为 $3$ ；
选择第 $3, 4, 5$ 根小木棍，长度之和为 $3 + 8 + 10 = 21$ ，长度最大值为 $10$ ；
选择第 $1, 2, 4, 5$ 根小木棍，长度之和为 $2 + 2 + 8 + 10 = 22$ ，长度最大值为 $10$ ；
选择第 $1, 3, 4, 5$ 根小木棍，长度之和为 $2 + 3 + 8 + 10 = 23$ ，长度最大值为 $10$ ；
选择第 $2, 3, 4, 5$ 根小木棍，长度之和为 $2 + 3 + 8 + 10 = 23$ ，长度最大值为 $10$ ；
选择第 $1, 2, 3, 4, 5$ 根小木棍，长度之和为 $2 + 2 + 3 + 8 + 10 = 25$ ，长度最大值为 $10$ 。

数据范围

对于所有测试数据，保证：

$3 \le n \le 5,000$ ；
对于所有 $1 \le i \le n$ ，均有 $1 \le a_i \le 5,000$ 。

测试点编号	$n \le$	$\max_{i=1}^{n} a_i \le$
$1 \sim 3$	$3$	$10$
$4 \sim 6$	$10$	$10^2$
$7 \sim 10$	$20$	$10^2$
$11 \sim 14$	$500$	$10^2$
$15 \sim 17$	$500$	$1$
$18 \sim 20$	$5,000$	$1$
$21 \sim 25$	$5,000$	$5,000$

部分分

12 分
测试点 $1 \sim 3$ ： $n \le 3$ ， $\max_{i=1}^{n} a_i \le 10$ 。
12 分
测试点 $4 \sim 6$ ： $n \le 10$ ， $\max_{i=1}^{n} a_i \le 10^2$ 。
16 分
测试点 $7 \sim 10$ ： $n \le 20$ ， $\max_{i=1}^{n} a_i \le 10^2$ 。
16 分
测试点 $11 \sim 14$ ： $n \le 500$ ， $\max_{i=1}^{n} a_i \le 10^2$ 。
12 分
测试点 $15 \sim 17$ ： $n \le 500$ ， $\max_{i=1}^{n} a_i \le 1$ 。
12 分
测试点 $18 \sim 20$ ： $n \le 5,000$ ， $\max_{i=1}^{n} a_i \le 1$ 。
20 分
测试点 $21 \sim 25$ ： $n \le 5,000$ ， $\max_{i=1}^{n} a_i \le 5,000$ 。

原文保真说明：原卷印刷错误 2 处（照原卷保留，未作修改）

原卷印刷如此其它数据范围
原卷作 | $15 \sim 17$ | $500$ | $1$ |
原卷测试点表中该档 max a_i 上界印作单独一个 1（原件第 13 页，900 dpi 复核确认无上标、无千分位，文本层同样只有 1）。上界存疑但不与整体范围矛盾（所有木棍长度均为 1 时拼成条件退化为 m>2，是自洽的纯组合特例档），照录不改；下游不得据此改写为 10^3 / 1,000。
原卷印刷如此其它数据范围
原卷作 | $18 \sim 20$ | $5,000$ | $1$ |
同上：该档 max a_i 上界亦印作单独一个 1，照录不改。

你的代码（C++）

提交后由评测机编译运行，结果见下方

编辑器加载中…

76 B / 64 KB

简单背包与区间类型动态规划