首页 > ACM题库 > HDU-杭电 > hdu 3946-philosophy girl’s trail-贪心-[解题报告]hoj
2015
04-14

hdu 3946-philosophy girl’s trail-贪心-[解题报告]hoj

Philosophy Girl’s Trail

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 719    Accepted Submission(s): 208



Problem Description
  Philosophy Girl Krolia was always on the go. No one could figure out where she was. It’s said that she traveled all over the world with only two kinds of items:books and staffs.
  Krolia had a knapsack which is composed of n*m grids, and every item can be fit into grids. All the books’ size is 1*2(2*1), and the staffs’ is 1*3(3*1) and each of them can be rotated 90, 180 or 270 degrees. Every item is assigned a value and Krolia wanted
to go with the maximal value.
 


Input
  The first line comes with one integer T (T=100) which denotes the test cases.
  In the first line of each case, there is four integers n (1<=n<=500), m (1<=m<=500), n1 (1<=n1<=10000) and n2 (1<=n2<=10000) which indicates the size of the knapsack, the number of the optional books and staffs. 
  The next line contains n1 integers which indicate the value bi (0<=bi<=1000) of every book. 
  The last line contains n2 integers si (0<=si<=1000) which indicate the value of every staff.
 


Output
  For each test case, output one line.
  First, output "Case #C: ", where C is the number of test case, from 1 to T. Then output the maximal value.
 


Sample Input
2 2 3 2 2 1 2 1 2 4 4 4 4 1 1 2 2 10 10 10 10
 


Sample Output
Case #1: 4 Case #2: 44
Hint
n,m,n1 and n2 <=100 in 20 cases. 50<=n,m<=500 and 1000<=n1,n2<=2000 in 50 cases. 100<=n,m<=200 and 9000<=n1,n2<=10000 in 30 cases.
 


Author
[email protected] Fans Club
 


Source
 
贪心证明见:http://acm.hdu.edu.cn/discuss/problem/post/reply.php?postid=4547&messageid=1&deep=0
AC代码:
#include<algorithm>
#include<iostream>
#include<cstdio>
using namespace std;
#define maxn 10010
int m,n,n1,n2;
int mb,ms;
int b[maxn],s[maxn];
int cmp(int t1,int t2){
    return t1>t2;
}
int main(){
    int T; scanf("%d",&T);
    for(int cas=1;cas<=T;cas++){
        scanf("%d%d%d%d",&n,&m,&n1,&n2);
        s[0]=b[0]=0;
        for(int i=1;i<=n1;i++)
            scanf("%d",&b[i]);
        sort(b+1,b+1+n1,cmp);

        for(int i=1;i<=n2;i++)
            scanf("%d",&s[i]);
        sort(s+1,s+1+n2,cmp);

        for(int i=1;i<=n1;i++)
            b[i]+=b[i-1];
        for(int i=1;i<=n2;i++)
            s[i]+=s[i-1];

        if(n<=1 && m<=1){
            printf("Case #%d: 0\n",cas);
        }
        else{
            if(n>m)
                swap(n,m);
            int ans=0;
            mb=min(n1,n*m/2);

            if(n==1)
                ms=min(n2,n*m/3);
            else if(n==2 && m%3==2)
                ms=min(n2,n*m/3-1);
            else
                ms=min(n2,n*m/3);

            int msize=n*m;
            for(int i=0;i<=ms;i++){
                int tmp=0;
                int j=(msize-i*3)/2;
                tmp+=s[i];
                if(j<=mb)
                    tmp+=b[j];
                else
                    tmp+=b[mb];
                if(tmp>ans)
                    ans=tmp;
            }
            printf("Case #%d: %d\n",cas,ans);
        }
    }
    return 0;
}

版权声明:本文为博主原创文章,未经博主允许不得转载。


  1. 第2题,TCP不支持多播,多播和广播仅应用于UDP。所以B选项是不对的。第2题,TCP不支持多播,多播和广播仅应用于UDP。所以B选项是不对的。