济南学习 Day1 T3 am

凝视
【问题描述】
背包是个好东西，希望我也有。
给你一个二维的背包，它的体积是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 ;

 }

巴特西

济南学习 Day1 T3 am

最新文章

热门文章