Python 竞赛模板 输入输出 import sys input = sys.stdin.readline sys.setrecursionlimit(10**6) n = int(input()) a, b = map(int, input().split()) arr = list(map(int, input().split())) for _ in ran

Two Sets II 题解 题目描述 https://cses.fi/problemset/task/1092 给定数字 1, 2, …, n，求将其分成两个和相等集合的方式数。 限制： - 1 ≤ n ≤ 500 示例： - 输入：7 - 输出：4 - 解释： - {1,3,4,6} 和 {2,5,7} - {1,2,5,6} 和 {3,4,7} - {1,2,4,7} 和 {3,

Minimizing Coins（最少硬币数） 题目描述 https://cses.fi/problemset/task/1634/ 给定 n 种硬币，每种硬币价值为 ci，求凑成金额 x 所需的最少硬币数（每种硬币可用无限次）。如果无法凑成，输出 -1。 限制： - 1 ≤ n ≤ 100 - 1 ≤ x ≤ 106 - 1 ≤ c_i ≤ 106 解法 问题类型：完全背包

完全背包类型一：计数问题（方案数） Coin Combinations I（有序） 题目描述 https://cses.fi/problemset/task/1635 给定 n 种硬币，每种硬币价值为 ci，求凑成金额 x 的不同方式数（顺序不同视为不同）。输出模 109 + 7 的结果。 限制： - 1 ≤ n ≤ 100 - 1 ≤ x ≤ 106 - 1 ≤ c_i ≤ 106

完全背包问题 什么是完全背包 完全背包（Unbounded Knapsack） 是动态规划中的经典问题： 有 n 种物品，每种物品有重量/价值 wi，每种物品可以无限次使用，求恰好凑成重量 W 的方案数或最大价值。 特点 物品数量无限：每种物品可以重复使用多次 状态无后效性：只关心当前重量，不关心用了哪些物品 组合方式：求的是组合（无序）还是排列（有序） 做题方

0/1 背包问题 问题描述 有 N 件物品，每件物品有重量 wi 和价值 vi，求在不超过背包容量 W 的情况下，选择物品使得总价值最大。 一维 DP 定义：dp[j] 为背包容量为 j 时的最大价值 初始条件：dp[j] = 0 状态转移： dp[j] = max (dp[j], dp[j − w] + v) 代码： N, W = map(int, input().

背包 DP 背包问题简介 背包问题通常涉及将有限容量的容器用物品的子集填满，我们希望计算或优化与物品相关的某些数量。几乎每次，你可以将每个物品视为具有正重量，而我们选择的物品的总重量不得超过容器的容量，这个容量是一个数字。 背包问题的变体 0/1 背包问题: 选择物品的子集，使得它们总价值最大化，且总重量不超过容器容量 完全背包问题: 找到所有可能的、由任何物品子集实现的总重量，

Money Sums 题解 题目描述 https://cses.fi/problemset/task/1740 给定 n 枚硬币，每枚硬币价值 xi，求能凑成的所有不同金额。 限制： - 1 ≤ n ≤ 100 - 1 ≤ xi ≤ 1000 示例： - 输入：4, coins = [4, 2, 5, 2] - 输出：9 种金额：2 4 5 6 7 8 9 11 13 解法 问

Dice Combinations 题解 题目描述 https://cses.fi/problemset/task/1633 给定一个目标整数 N，计算有多少种骰子投掷序列，使得骰子顶面的和为 N。 限制：1 ≤ N ≤ 106 解法 问题类型：完全背包（计数问题，每种骰子点数可用无限次） 定义：dp[i] 为掷骰子得到的和为 i 的所有序列的数量 初始条件：dp[0] =

Book Shop 题解 题目描述 https://cses.fi/problemset/task/1158 给定 n 本书，每本书有价格 hi 和页数 si，总预算为 x，求在预算范围内能获得的最大页数。每本书只能购买一次。 限制： - 1 ≤ n ≤ 1000 - 1 ≤ x ≤ 105 - 1 ≤ h_i, s_i ≤ 1000 示例： - 输入：4 10, h = [4, 8,