凝视
【问题描述】
背包是个好东西，希望我也有。
给你一个二维的背包，它的体积是N*M。现在你有一些大小为1× 2和1×
3的物品，每个物品有自己的价值。你希望往背包里面装一些物品，使得它们的
价值和最大，问最大的价值和是多少。
【输入格式】
第一行一个整数T代表该测试点的数据组数。
对于每组数据，第一行有四个整数N,M,n1,n2其中n1 ,n2 分别代表大小为
1× 2和大小为1 × 3的物品个数。
1 × 2 接下来一行有? 2 个数代表每个1 × 3物品的价值。
【输出格式】
对于每组询问，输出能够达到的价值最大值。
【样例输入】
1
2 3 2 2
1 2
1 2
【样例输出】
4
【样例解释】
庙里有座山。
【数据规模与约定】
对于20%的数据，N,M<=10,n1,n2<=100
70%的数据，N,M ≤ 100,n1,n2 ≤ 2000。
对于100%的数据，1 ≤ T ≤ 10,1 ≤ N,M ≤ 500,0 ≤ n1,n2 ≤ 10000。
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=;
int n,m,n1,n2,y[maxn],z[maxn],sum[maxn];
bool cmp(int a,int b)
{
return a>b;
}
int main()
{
freopen("eyesight.in","r",stdin);
freopen("eyesight.out","w",stdout); int t;
scanf("%d",&t);
while(t--)
{
scanf("%d%d%d%d",&n,&m,&n1,&n2);
for (int a=;a<=n1;a++)
scanf("%d",&y[a]);
for (int a=;a<=n2;a++)
scanf("%d",&z[a]);
sort(y+,y+n1+,cmp);
sort(z+,z+n2+,cmp);
for (int a=;a<=n1;a++)
y[a]+=y[a-];
for (int a=;a<=n2;a++)
z[a]+=z[a-];
int delta;
if (n%== && m%== && (n== || m==)) delta=;
else delta=n*m%;
int ans=,limit=min(n2,(n*m-delta)/);
for (int a=;a<=limit;a++)
ans=max(ans,z[a]+y[min(n1,(n*m-a*)>>)]);
printf("%d\n",ans);
} return ;
}