A4784 | $异格背包问题$

时间限制1s

内存限制256MB

通过 / 提交0/0

题目描述

考虑一个异格（不一样）的背包问题：背包变成 $N \times M$ （$N$ 行 $M$ 列）的矩阵。你希望在其中合理放置物品，以获得最大的价值和。 需要注意的是，物品的大小只可能为 $1\times 2$ 或者 $1\times 3$ ，并且在放置物品的时候，物品都可以做九十度的旋转。

第一行一个整数 $T$ 代表该测试点的数据组数。 对于每组数据，第一行有四个整数 $N,M,n_1,n_2$ ，其中 $n_1,n_2$ 分别代表大小为 $1\times 2$ 和大小为 $1\times 3$ 的物品个数。 接下来一行有 $n_1$ 个数代表每个 $1\times 2$ 物品的价值。 接下来一行有 $n_2$ 个数代表每个 $1\times 3$ 物品的价值。

对于每组询问，输出能够达到的价值最大值。

输入 #1

输出 #1

C++ 编辑器

输入

输出