题解

我们发现选哪件相同大小的物品都是一样的，所以尽量填满背包，在选的时候直接挑最大的。

我们又注意到当 $N\gt 2$ 且 $M\gt 2$ 且有足够多的 $1\times 3$ 的物品时，不管放多少个 $1\times 2$ 的物品都能使剩余面积最小值小于 $3$。

所以我们可以分类讨论：

1. 当 $N,M$ 足够大时，我们枚举填 $1\times 2$ 物品的个数，用面积计算最多放置 $1\times 3$ 的物品个数，得出最小值。
2. 当 $N,M$ 非常小时，我们直接暴力计算。

//双指针枚举当放x个1*2物品时能放多少1*3物品 
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <memory.h>
#define int long long
using namespace std;
int a[250005], b[250005];
int n, m, n1, n2;
int solve_m_little(){//计算当n<=2&&m<=2的值
	if(n == 1){
		if(m == 1) return 0;
		return a[1];
	}else{
		if(m == 1) return a[1];
		return a[1] + a[2];
	}
}
void solve(){
	memset(a, 0, sizeof(a));//数组不清空祖宗都见不到（
	memset(b, 0, sizeof(b));
	cin >> n >> m >> n1 >> n2;
	for(int i = 1; i <= n1; i++) cin >> a[i];
	for(int i = 1; i <= n2; i++) cin >> b[i];
	sort(a + 1, a + n1 + 1, greater <int>());//从大到小排序
	sort(b + 1, b + n2 + 1, greater <int>());
	if(n <= 2 && m <= 2){//特判
		cout << solve_m_little() << '\n';
		return;
	}
	for(int i = 1; i <= n * m; i++) a[i] += a[i - 1];//预处理前缀和，表示选前 i 件物品的价值
	for(int i = 1; i <= n * m; i++) b[i] += b[i - 1];
	int ans = 0;
	for(int i = 1; i <= n * m / 2; i++){//枚举
		int j = (n * m - i * 2) / 3;//通过面积计算最多数量
		ans = max(ans, a[i] + b[j]);//记录最大值
	}
	cout << ans << '\n';
}
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	int t;
	cin >> t;
	while(t--) solve();

	return 0;
}

时间复杂度 $O(T\times N\times M)$。
为什么我要预处理这么多项前缀和？理由如下：
请输入文本