刷题记录||背包动态规划

👾背包动态规划

背包动态规划是线性动态规划中特殊的一类，NOIP中考到的次数也不少。

🍊[P1048]采药

[NOIP2005 普及组] 采药

题目描述

辰辰是个天资聪颖的孩子，他的梦想是成为世界上最伟大的医师。为此，他想拜附近最有威望的医师为师。医师为了判断他的资质，给他出了一个难题。医师把他带到一个到处都是草药的山洞里对他说：“孩子，这个山洞里有一些不同的草药，采每一株都需要一些时间，每一株也有它自身的价值。我会给你一段时间，在这段时间里，你可以采到一些草药。如果你是一个聪明的孩子，你应该可以让采到的草药的总价值最大。”

如果你是辰辰，你能完成这个任务吗？

输入格式

第一行有 $2$ 个整数 $T$（$1 \le T \le 1000$）和 $M$（$1 \le M \le 100$），用一个空格隔开，$T$ 代表总共能够用来采药的时间，$M$ 代表山洞里的草药的数目。

接下来的 $M$ 行每行包括两个在 $1$ 到 $100$ 之间（包括 $1$ 和 $100$）的整数，分别表示采摘某株草药的时间和这株草药的价值。

输出格式

输出在规定的时间内可以采到的草药的最大总价值。

样例 #1

样例输入 #1
70 3
71 100
69 1
1 2
样例输出 #1
3
提示

【数据范围】

对于 $30%$ 的数据，$M \le 10$；

对于全部的数据，$M \le 100$。

【题目来源】

NOIP 2005 普及组第三题

🎈AC代码

#include<bits/stdc++.h>
using namespace std;
const int maxm = 150;
int w[maxm], t[maxm];
long long dp[maxm][maxm * 10];
int main() {
    int ts, m;cin >> ts >> m;
    for (int i = 1;i <= m;i++)
        cin >> t[i] >> w[i];
    for (int i = 1;i <= m;i++) {
        for (int j = ts;j >= 0;j--) {
            if (j >= t[i])
                dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - t[i]] + w[i]);
            else {
                dp[i][j] = dp[i - 1][j];
            }
        }
    }

    cout << dp[m][ts] << endl;

    return 0;
}

🍊[P1060]开心的金明

[NOIP2006 普及组] 开心的金明

题目描述

金明今天很开心，家里购置的新房就要领钥匙了，新房里有一间他自己专用的很宽敞的房间。更让他高兴的是，妈妈昨天对他说：“你的房间需要购买哪些物品，怎么布置，你说了算，只要不超过 $N$ 元钱就行”。今天一早金明就开始做预算，但是他想买的东西太多了，肯定会超过妈妈限定的 $N$ 元。于是，他把每件物品规定了一个重要度，分为 $5$ 等：用整数 $1-5$ 表示，第 $5$ 等最重要。他还从因特网上查到了每件物品的价格（都是整数元）。他希望在不超过 $N$ 元（可以等于 $N$ 元）的前提下，使每件物品的价格与重要度的乘积的总和最大。

设第$j$件物品的价格为 $v_j$，重要度为 $w_j$，共选中了 $k$ 件物品，编号依次为 $j_1,j_2,…,j_k$，则所求的总和为：

$v_{j_1} \times w_{j_1}+v_{j_2} \times w_{j_2} …+v_{j_k} \times w_{j_k}$。

请你帮助金明设计一个满足要求的购物单。

输入格式

第一行，为 $2$ 个正整数，用一个空格隔开：$n,m$（$n<30000,m<25$）其中 $n$ 表示总钱数，$m$ 为希望购买物品的个数。

从第 $2$ 行到第 $m+1$ 行，第 $j$ 行给出了编号为 $j-1$ 的物品的基本数据，每行有 $2$ 个非负整数 $v,p$（其中 $v$ 表示该物品的价格 $(v \le 10000)$，$p$ 表示该物品的重要度（$1\le p\le5$）。

输出格式

$1$ 个正整数，为不超过总钱数的物品的价格与重要度乘积的总和的最大值（$<100000000$）。

样例 #1

样例输入 #1
1000 5
800 2
400 5
300 5
400 3
200 2
样例输出 #1
3900
提示

NOIP 2006 普及组第二题

🍊[P1855]榨取kkksc03

榨取kkksc03

题目描述

洛谷 2 的团队功能是其他任何 OJ 和工具难以达到的。借助洛谷强大的服务器资源，任何学校都可以在洛谷上零成本的搭建 OJ 并高效率的完成训练计划。

为什么说是搭建 OJ 呢？为什么高效呢？

因为，你可以上传私有题目，团队外别人是无法看到的。我们还能帮你们评测！

你可以创建作业，给组员布置任务，查看组员的完成情况，还可以点评任意一份代码！

你可以创建比赛！既可以是 OI 赛制还可以是 ICPC 赛制！既可以是团队内部的私有比赛，也可以公开赛，甚至可以指定谁可以参加比赛。这样，搞“x 校联赛”最合适不过了。洛谷凭借这个功能，希望能够提供公开及私有比赛的另外一个平台。

值得说明的是，本次比赛就是采用团队私有题目+邀请比赛的机制。

洛谷的运营组决定，如果一名 OIer 向他的教练推荐洛谷，并能够成功的使用（成功使用的定义是：该团队有 $20$ 个或以上的成员，上传 $10$ 道以上的私有题目，布置过一次作业并成功举办过一次公开比赛），那么他可以浪费掉 kkksc03 的一些时间的同时消耗掉 kkksc03 的一些金钱以满足自己的一个愿望。

kkksc03 的时间和金钱是有限的，所以他很难满足所有同学的愿望。所以他想知道在自己的能力范围内，最多可以完成多少同学的愿望？

输入格式

第一行三个整数 $n,M,T$，表示一共有 $n$（$1 \le n \le 100$）个愿望， kkksc03 的手上还剩 $M$（$0 \le M \le 200$）元，他的暑假有 $T$（$0 \le T \le 200$）分钟时间。

第 $2$~$n+1$ 行 $m_{i}$ , $t_{i}$ 表示第 $i$ 个愿望所需要的金钱和时间。

输出格式

一行，一个数，表示 kkksc03 最多可以实现愿望的个数。

样例 #1

样例输入 #1
6 10 10
1 1
2 3 
3 2
2 5
5 2
4 3
样例输出 #1
4

🍊[P5020]货币系统

[NOIP2018 提高组] 货币系统

题目背景

NOIP2018 提高组 D1T2

题目描述

在网友的国度中共有 $n$ 种不同面额的货币，第 $i$ 种货币的面额为 $a[i]$，你可以假设每一种货币都有无穷多张。为了方便，我们把货币种数为 $n$、面额数组为 $a[1..n]$ 的货币系统记作 $(n,a)$。

在一个完善的货币系统中，每一个非负整数的金额 $x$ 都应该可以被表示出，即对每一个非负整数 $x$，都存在 $n$ 个非负整数 $t[i]$ 满足 $a[i] \times t[i]$ 的和为 $x$。然而，在网友的国度中，货币系统可能是不完善的，即可能存在金额 $x$ 不能被该货币系统表示出。例如在货币系统 $n=3$, $a=[2,5,9]$ 中，金额 $1,3$ 就无法被表示出来。

两个货币系统 $(n,a)$ 和 $(m,b)$ 是等价的，当且仅当对于任意非负整数 $x$，它要么均可以被两个货币系统表出，要么不能被其中任何一个表出。

现在网友们打算简化一下货币系统。他们希望找到一个货币系统 $(m,b)$，满足 $(m,b)$ 与原来的货币系统 $(n,a)$ 等价，且 $m$ 尽可能的小。他们希望你来协助完成这个艰巨的任务：找到最小的 $m$。

输入格式

输入文件的第一行包含一个整数 $T$，表示数据的组数。

接下来按照如下格式分别给出 $T$ 组数据。每组数据的第一行包含一个正整数 $n$。接下来一行包含 $n$ 个由空格隔开的正整数 $a[i]$。

输出格式

输出文件共有 $T$ 行，对于每组数据，输出一行一个正整数，表示所有与 $(n,a)$ 等价的货币系统 $(m,b)$ 中，最小的 $m$。

样例 #1

样例输入 #1
2 
4 
3 19 10 6 
5 
11 29 13 19 17
样例输出 #1
2   
5
提示

在第一组数据中，货币系统 $(2, [3,10])$ 和给出的货币系统 $(n, a)$ 等价，并可以验证不存在 $m < 2$ 的等价的货币系统，因此答案为 $2$。在第二组数据中，可以验证不存在 $m < n$ 的等价的货币系统，因此答案为 $5$。

【数据范围与约定】

对于 $100%$ 的数据，满足 $1 ≤ T ≤ 20, n,a[i] ≥ 1$。

🍊[P1757]通天之分组背包

通天之分组背包

题目背景

直达通天路·小 A 历险记第二篇

题目描述

自 $01$ 背包问世之后，小 A 对此深感兴趣。一天，小 A 去远游，却发现他的背包不同于 $01$ 背包，他的物品大致可分为 $k$ 组，每组中的物品相互冲突，现在，他想知道最大的利用价值是多少。

输入格式

两个数 $m,n$，表示一共有 $n$ 件物品，总重量为 $m$。

接下来 $n$ 行，每行 $3$ 个数 $a_i,b_i,c_i$，表示物品的重量，利用价值，所属组数。

输出格式

一个数，最大的利用价值。

样例 #1

样例输入 #1
45 3
10 10 1
10 5 1
50 400 2
样例输出 #1
10
提示

$1 \leq m, n \leq 1000$，$1\leq k\leq 100$，$a_i, b_i, c_i$ 在 int 范围内。

🍊[P1064]金明的预算方案

[NOIP2006 提高组] 金明的预算方案

题目描述

金明今天很开心，家里购置的新房就要领钥匙了，新房里有一间金明自己专用的很宽敞的房间。更让他高兴的是，妈妈昨天对他说：“你的房间需要购买哪些物品，怎么布置，你说了算，只要不超过 $n$ 元钱就行”。今天一早，金明就开始做预算了，他把想买的物品分为两类：主件与附件，附件是从属于某个主件的，下表就是一些主件与附件的例子：

主件附件
电脑打印机，扫描仪
书柜图书
书桌台灯，文具
工作椅无

如果要买归类为附件的物品，必须先买该附件所属的主件。每个主件可以有 $0$ 个、$1$ 个或 $2$ 个附件。每个附件对应一个主件，附件不再有从属于自己的附件。金明想买的东西很多，肯定会超过妈妈限定的 $n$ 元。于是，他把每件物品规定了一个重要度，分为 $5$ 等：用整数 $1 \sim 5$ 表示，第 $5$ 等最重要。他还从因特网上查到了每件物品的价格（都是 $10$ 元的整数倍）。他希望在不超过 $n$ 元的前提下，使每件物品的价格与重要度的乘积的总和最大。

设第 $j$ 件物品的价格为 $v_j$，重要度为$w_j$，共选中了 $k$ 件物品，编号依次为 $j_1,j_2,\dots,j_k$，则所求的总和为：

$v_{j_1} \times w_{j_1}+v_{j_2} \times w_{j_2}+ \dots +v_{j_k} \times w_{j_k}$。

请你帮助金明设计一个满足要求的购物单。

输入格式

第一行有两个整数，分别表示总钱数 $n$ 和希望购买的物品个数 $m$。

第 $2$ 到第 $(m + 1)$ 行，每行三个整数，第 $(i + 1)$ 行的整数 $v_i$，$p_i$，$q_i$ 分别表示第 $i$ 件物品的价格、重要度以及它对应的的主件。如果 $q_i=0$，表示该物品本身是主件。

输出格式

输出一行一个整数表示答案。

样例 #1

样例输入 #1
1000 5
800 2 0
400 5 1
300 5 1
400 3 0
500 2 0
样例输出 #1
2200
提示

数据规模与约定

对于全部的测试点，保证 $1 \leq n \leq 3.2 \times 10^4$，$1 \leq m \leq 60$，$0 \leq v_i \leq 10^4$，$1 \leq p_i \leq 5$，$0 \leq q_i \leq m$，答案不超过 $2 \times 10^5$。

主件	附件
电脑	打印机，扫描仪
书柜	图书
书桌	台灯，文具
工作椅	无

🍊[P2946]Cow Frisbee Team

[USACO09MAR] Cow Frisbee Team S

题目描述

老唐最近迷上了飞盘，约翰想和他一起玩，于是打算从他家的 $N$ 头奶牛中选出一支队伍。

每只奶牛的能力为整数，第 $i$ 头奶牛的能力为$R_i$ 。飞盘队的队员数量不能少于 $1$、大于$N$。一支队伍的总能力就是所有队员能力的总和。

约翰比较迷信，他的幸运数字是 $F$ ，所以他要求队伍的总能力必须是 $F$ 的倍数。请帮他

算一下，符合这个要求的队伍组合有多少？由于这个数字很大，只要输出答案对 $10^8$ 取模的值。

输入格式

第一行：两个用空格分开的整数：$N$ 和 $F$。

第二行到 $N+1$ 行：第 $i+1$ 行有一个整数$R_i$ ，表示第 $i$ 头奶牛的能力。

输出格式

第一行：单个整数，表示方案数对 $10^8$ 取模的值。

样例 #1

样例输入 #1
4 5 
1 
2 
8 
2
样例输出 #1
3
提示

数据范围与约定

对于 $100%$ 的数据，$1 \le N \le 2000$，$1 \le F \le 1000$ ，$1 \le R_i \le 10^5$ 。

🍊[P1156]垃圾陷阱

垃圾陷阱

题目描述

卡门――农夫约翰极其珍视的一条 Holsteins 奶牛――已经落了到 “垃圾井” 中。“垃圾井” 是农夫们扔垃圾的地方，它的深度为 $D$（$2 \le D \le 100$）英尺。

卡门想把垃圾堆起来，等到堆得与井同样高时，她就能逃出井外了。另外，卡门可以通过吃一些垃圾来维持自己的生命。

每个垃圾都可以用来吃或堆放，并且堆放垃圾不用花费卡门的时间。

假设卡门预先知道了每个垃圾扔下的时间 $t$（$1 \le t \le 1000$），以及每个垃圾堆放的高度 $h$（$1 \le h \le 25$）和吃进该垃圾能维持生命的时间 $f$（$1 \le f \le 30$），要求出卡门最早能逃出井外的时间，假设卡门当前体内有足够持续 $10$ 小时的能量，如果卡门 $10$ 小时内（不含 $10$ 小时，维持生命的时间同）没有进食，卡门就将饿死。

输入格式

第一行为两个整数，$D$ 和 $G$（$1 \le G \le 100$），$G$ 为被投入井的垃圾的数量。

第二到第 $G+1$ 行每行包括三个整数：$T$（$1 \le T \le 1000$），表示垃圾被投进井中的时间；$F$（$1 \le F \le 30$），表示该垃圾能维持卡门生命的时间；和 $H$（$1 \le H \le 25$），该垃圾能垫高的高度。

输出格式

如果卡门可以爬出陷阱，输出一个整数，表示最早什么时候可以爬出；否则输出卡门最长可以存活多长时间。

样例 #1

样例输入 #1
20 4
5 4 9
9 3 2
12 6 10
13 1 1
样例输出 #1
13
提示

【样例说明】

卡门堆放她收到的第一个垃圾：$\mathrm{height}=9$；

卡门吃掉她收到的第 $2$ 个垃圾，使她的生命从 $10$ 小时延伸到 $13$ 小时；

卡门堆放第 $3$ 个垃圾，$\mathrm{height}=19$；

卡门堆放第 $4$ 个垃圾，$\mathrm{height}=20$。

🍊[P5322]排兵布阵

[BJOI2019] 排兵布阵

题目描述

小 C 正在玩一款排兵布阵的游戏。在游戏中有 $n$ 座城堡，每局对战由两名玩家来争夺这些城堡。每名玩家有 $m$ 名士兵，可以向第 $i$ 座城堡派遣 $a_i$ 名士兵去争夺这个城堡，使得总士兵数不超过 $m$。

如果一名玩家向第 $i$ 座城堡派遣的士兵数严格大于对手派遣士兵数的两倍，那么这名玩家就占领了这座城堡，获得 $i$ 分。

现在小 C 即将和其他 $s$ 名玩家两两对战，这 $s$ 场对决的派遣士兵方案必须相同。小 C 通过某些途径得知了其他 $s$ 名玩家即将使用的策略，他想知道他应该使用什么策略来最大化自己的总分。

由于答案可能不唯一，你只需要输出小 C 总分的最大值。

输入格式

输入第一行包含三个正整数 $s,n,m$，分别表示除了小 C 以外的玩家人数、城堡数和每名玩家拥有的士兵数。
接下来 $s$ 行，每行 $n$ 个非负整数，表示一名玩家的策略，其中第 $i$ 个数 $a_i$ 表示这名玩家向第 $i$ 座城堡派遣的士兵数。

输出格式

输出一行一个非负整数，表示小 C 获得的最大得分。

样例 #1

样例输入 #1
1 3 10
2 2 6
样例输出 #1
3
样例 #2

样例输入 #2
2 3 10
2 2 6
0 0 0
样例输出 #2
8
提示

样例1解释：
小 C 的最佳策略为向第 $1$ 座城堡和第 $2$ 座城堡各派遣 $5$ 名士兵。

样例2解释：
小 C 的最佳策略之一为向第 $1$ 座城堡派遣 $2$ 名士兵，向第 $2$ 座城堡派遣 $5$ 名士兵，向第 $3$ 座城堡派遣 $1$ 名士兵。

数据范围：
对于 $10%$ 的数据： $s=1,n \le 3,m \le 10$
对于 $20%$ 的数据： $s=1,n \le 10,m \le 100$
对于 $40%$ 的数据： $n\le 10,m\le 100$
对于另外 $20%$ 的数据： $s=1$
对于 $100%$ 的数据：
$1\le s \le 100$
$1\le n \le 100$
$1\le m \le 20000$
对于每名玩家 $a_i \ge 0$，$\sum\limits_{i=1}^n a_i \le m$

🍊[P5289]皮配

[十二省联考 2019] 皮配

题目背景

一年一度的综艺节目《中国好码农》又开始了。本季度，好码农由 Yazid、Zayid、小 R、大 R 四位梦想导师坐镇，他们都将组建自己的梦想战队，并率领队员向梦想发起冲击。

四位导师的派系不尽相同，节目组为了营造看点，又将导师分成了不同的阵营，与此同时对不同阵营、不同派系都作出了战队总人数限制：

四位导师分成两个阵营：

Yazid、小 R 两位导师组成蓝阵营，他们两位的战队人数总和不得超过 $C_0$。

Zayid、大 R 两位导师组成红阵营，他们两位的战队人数总和不得超过 $C_1$。

四位导师分成两个派系：

Yazid、Zayid 两位导师属于鸭派系，他们两位的战队人数总和不得超过 $D_0$。

小 R、大 R 两位导师属于 R 派系，他们两位的战队人数总和不得超过 $D_1$。

题目描述

本季好码农邀请到了全国各路学生精英参赛。他们来自全国 $c$ 个城市的 $n$ 所不同学校（城市的编号从 $1$ 至 $c$，学校的编号从 $1$ 至 $n$）。其中，第 $i$ 所学校所属的城市编号为 $b_i$，且共有 $s_i$ 名选手参赛。

在【题目背景】中提到的各总人数限制之外，本季度《中国好码农》的导师选择阶段有额外规则如下：

来自同城市的所有选手必须加入相同的阵营。

来自同学校的所有选手必须选择相同的导师。

对于导师，大部分学校的学生对导师没有偏好。但是有 $k$ 所学校，其中每所学校的学生有且仅有一位他们不喜欢的导师。同一所学校的学生不喜欢的导师相同，他们不会加入他们不喜欢的导师的战队。

面对琳琅满目的规则和选手的偏好，作为好码农忠实观众的你想计算出，在所有选手都进行了战队选择后，战队组成共有多少种可能的局面？

两种战队组成的局面被认为是不同的，当且仅当在存在一所学校，使得在这两种局面中这所学校的选手加入了不同导师的战队。

由于答案可能很大，你只需输出可能局面数对 $998244353$ 取模的结果即可。

输入格式

单个测试点中包含多组数据，输入的第一行包含一个非负整数 $T$ 表示数据组数。接下来依次描述每组数据，对于每组数据：

第 $1$ 行 $2$ 个正整数 $n$, $c$，分别表示学校数目、城市数目。

第 $2$ 行 $4$ 个正整数 $C_0$, $C_1$, $D_0$, $D_1$，分别表示题目中所描述的四个限制。

接下来 $n$ 行每行 $2$ 个正整数：

这部分中第 $i$ 行的两个数依次为 $b_i$, $s_i$，分别表示第 $i$ 所学校的所属城市以及选手数目。

保证 $b_i \leqslant c$，$s_i \leqslant\min\left{M, 10\right}$。其中 $M = \max \left{C_0, C_1, D_0, D_1\right}$。

接下来 $1$ 行一个非负整数 $k$，表示选手有偏好的学校数目。

接下来 $k$ 行，每行 $2$ 个整数 $i$, $p$，描述编号为 $i$ 的学校选手有偏好：

其中，$p$ 为一个 $0$ 至 $3$ 之间的整数，描述该校选手不喜欢的导师：$0$ 代表 Yazid，$1$ 代表小 R，$2$ 代表 Zayid，$3$ 代表大 R。

保证 $1 \leqslant i \leqslant n$，且各行的 $i$ 互不相同。

对于输入的每一行，如果其包含多个数，则用单个空格将它们隔开。

输出格式

依次输出每组数据的答案，对于每组数据：

一行一个整数，表示可能局面数对 $998244353$ 取模的结果。

样例 #1

样例输入 #1
2
2 1
3 2 2 2
1 1
1 2
1
1 0
4 2
10 30 20 30
1 6
2 4
1 7
2 4
2
2 3
3 1
样例输出 #1
1
22
提示

样例 1 解释

对于第 $1$ 组数据：

唯一的城市 $1$ 包含共 $3$ 名选手，但红阵营的总人数限制为 $2$，无法容纳这些选手，因此他们被迫只能选择蓝阵营。

在此基础上，由于 $1$ 号学校的选手不喜欢 Yazid 老师，因此他们就必须加入 R 派系的小 R 老师麾下。

由于 R 派系总人数限制为 $2$，因此小 R 老师战队无法容纳 $2$ 号学校的选手，所以他们只能被迫加入Yazid 老师战队。

综上所述，可能的局面仅有这一种。

对于第 $2$ 组数据：

一个显然的事实是，$1$ 号城市的所有选手都无法加入蓝阵营，这是因为 $1$ 号城市的选手总人数超过了蓝阵营的总人数限制，因此他们被迫全部加入红阵营。

对于 $2$ 号城市选手加入蓝阵营的情况，稍加计算可得出共有 $15$ 种可能的局面。

对于 $2$ 号城市选手加入红阵营的情况，稍加计算可得出共有 $7$ 种可能的局面。

综上所述，可能的局面数为 $15 + 7 = 22$ 种。

数据规模与约定

其中，$M = \max\left{C_0, C_1, D_0, D_1\right}$。

对于所有测试点，保证 $T \leqslant5$。

对于所有测试点中的每一组数据，保证 $c \leqslant n \leqslant 1000$，$k \leqslant 30$，$M \leqslant 2500$，$1 \leqslant s_i \leqslant \min\left{M, 10\right}$。

另外，请你注意，数据并不保证所有的 $c$ 个城市都有参赛学校。

提示

另外还有两组附加样例文件，请在附件中下载。

十二省联考命题组温馨提醒您：

数据千万条，清空第一条。
多测不清空，爆零两行泪。