【模板】最长公共子序列 给定两个长度分别为 N 和 M 的字符串 A 和 B,求既是 A 的子序列又是 B 的子序列的字符串长度最长是多少。 输入格式第一行包含两个整数 N 和 M。 第二行包含一个长度为 N 的字符串,表示字符串 A。 第三行包含一个长度为 M 的字符串,表示字符串 B。 字符串均由小写字母构成。 输出格式输出一个整数,表示最大长度。 数据范围1≤N,M≤1000 输入样例:1234 5acbdabe 2021-05-14 模板 #DP
【模板】最长上升子序列及其优化 给定一个长度为 N 的数列,求数值严格单调递增的子序列的长度最长是多少。 输入格式第一行包含整数 N。 第二行包含 N 个整数,表示完整序列。 输出格式输出一个整数,表示最大长度。 数据范围1≤N≤1000,−109≤数列中的数≤109 输入样例:1273 1 2 1 8 5 6 输出样例14 模板123456789101112131415161718192021222324252627282 2021-05-14 模板
【模板】分组背包问题 有 N 组物品和一个容量是 V 的背包。 每组物品有若干个,同一组内的物品最多只能选一个。每件物品的体积是 vij,价值是 wij,其中 i 是组号,j 是组内编号。 求解将哪些物品装入背包,可使物品总体积不超过背包容量,且总价值最大。 输出最大价值。 输入格式第一行有两个整数 N,V,用空格隔开,分别表示物品组数和背包容量。 接下来有 N 组数据: 每组数据第一行有一个整数 Si,表示第 i 2021-03-26 模板 #背包问题 | DP
【模板】多重背包问题 有 N 种物品和一个容量是 V 的背包。 第 i 种物品最多有 si 件,每件体积是 vi,价值是 wi。 求解将哪些物品装入背包,可使物品体积总和不超过背包容量,且价值总和最大。输出最大价值。 输入格式第一行两个整数,N,V,用空格隔开,分别表示物品种数和背包容积。 接下来有 N 行,每行三个整数 vi,wi,si,用空格隔开,分别表示第 i 种物品的体积、价值和数量。 输出格式输出一个整数, 2021-03-25 模板 #背包问题 | DP