【问题描述】
背包是个好东西，希望我也有。
给你一个二维的背包，它的体积是? × ?。现在你有一些大小为1× 2和1×
3的物品，每个物品有自己的价值。你希望往背包里面装一些物品，使得它们的
价值和最大，问最大的价值和是多少。
【输入格式】
第一行一个整数?代表该测试点的数据组数。
对于每组数据，第一行有四个整数?,?,? 1 ,? 2 ，其中? 1 ,? 2 分别代表大小为
1× 2和大小为1 × 3的物品个数。
1 × 2 接下来一行有? 2 个数代表每个1 × 3物品的价值。
【输出格式】
对于每组询问，输出能够达到的价值最大值。
【样例输入】
1
2 3 2 2
1 2
1 2
【样例输出】
4
【样例解释】
庙里有座山，其实就是钟神。
【数据规模与约定】
2,? 1 ,? 2 ≤ 100。
70%的数据，?,? ≤ 100,? 1 ,? 2 ≤ 2000。
对于100%的数据，1 ≤ ? ≤ 10,1 ≤ ?,? ≤ 500,0 ≤ ? 1 ,? 2 ≤ 10000。
思路：
这题好恶心的我跟你讲；
做这个题的时候第一个反映是DP，然后风风火火的去打二维背包模板
打完回来一看傻了眼（这告诉我们要认真读题）
后来才知道这个题是个前缀和+枚举
那
怎么枚举呢？
这样枚举
判断体积为3的物品最多能放多少个
然后从0开始循环到max3
每次循环都用总体积减去已经放下的体积为3的物品的总体积
然后记录一下最大的ans就好了
恩
这是一个20分的做法
那
满分的做法呢？
满分的做法还要加一个小小的判断
现在我们想一下，所有的物体不能被拆分或者弯折
所以物体的长度一定要有足够的空间长度
但是
如果背包的长度==2或者背包的宽度==2
这时长度为3的物品就只能竖着放或者横着放
如果背包的宽度为2而长度为3的倍数（包括0）+2
这时最多能放下的体积为3的物体的个数为(n*m-4)/3
所以
如果一个背包的满足((m==2||n==2)&&m%3==2&&n%3==2)
则
能放下的体积为3的物品的个数为(n*m-4)/3
说到这基本就可以ac了
但是
不要急着去写代码
还有一个很重要的条件
就是个数最多不能超过体积为3的物品的总个数
或者是体积为2的物品的总个数
来，上代码：
#include<cstdio>
#include<cstring>
#include<algorithm> using namespace std; int T,sum2[],sum3[],n,m,n2,n3;
int min2,min3,max2,max3,sq,ans=,kcc; char ch; void qread(int &x)
{
x=;ch=getchar();
while(ch>''||ch<'') ch=getchar();
while(ch<=''&&ch>=''){x=x*+(int)(ch-'');ch=getchar();}
} bool cmp(int a,int b){return a>b;} int main()
{
qread(T);
while(T--)
{
ans=,min2=,min3=;
qread(n),qread(m),qread(n2),qread(n3);
for(int i=;i<=n2;i++) qread(sum2[i]);
for(int i=;i<=n3;i++) qread(sum3[i]);
sort(sum2+,sum2+n2+,cmp);
sort(sum3+,sum3+n3+,cmp);
for(int i=;i<=n2;i++) sum2[i]+=sum2[i-];
for(int i=;i<=n3;i++) sum3[i]+=sum3[i-];
sq=n*m;
if((n%==&&m%==)&&(n==||m==)) max3=(sq-)/;
else max3=sq/;
int kol=;
max3=min(max3,n3);
for(int i=min3;i<=max3;i++)
{
kol=;
kol+=sum3[i];
kcc=(sq-(i*))/;
kcc=min(n2,kcc);
kol+=sum2[kcc];
ans=max(ans,kol);
}
printf("%d\n",ans);
}
return ;
}