hihocoder 1271–舰队游戏

题目链接:https://hihocoder.com/problemset/problem/1271

描述

小Hi最近在玩一款组建舰队出海进行战争的游戏,在这个游戏中,小Hi需要根据需要组建一只舰队,一支舰队里最多同时存在N艘舰船,每艘舰船最多同时装备M个装备。

在一次关卡中,小Hi希望能够组建一只仅由航母构成的舰队,这意味着所有舰船的装备都是某种类型的飞机,小Hi将要使用的飞机有两种类型:对空飞机和对舰飞机,顾名思义,对空飞机用于和敌对舰船搭载的飞机进行对抗,而对舰飞机则直接用于攻击敌对舰船本身。

每艘航母的M个装备栏位是不一样的,我们可以用“搭载量”来对其进行量化描述,有些装备栏位的搭载量较高,有些装备栏位的搭载量较低,对于第i艘舰船,我们用Ai,j表示其第j个装备栏位的搭载量。

小Hi的军备库里有T架飞机,我们Bi表示第i架飞机的对空攻击力,并用Ci表示第i架飞机的对舰攻击力,其中对空飞机的对舰攻击力为0,对舰飞机的对空攻击力为0。

为舰船装备飞机,会提高舰队的“制空值”和“伤害值”。舰队的制空值为所有飞机的对空攻击力与其对应的装备栏位的搭载量的乘积之和,即:

制空值=

其中pi,j表示放置在第i艘舰船的第j个装备栏位的飞机编号。同理,舰队的伤害值为所有飞机的对舰攻击力与其对应的装备栏位的搭载量的乘积之和,即:

伤害值=

为了能够顺利的通过关卡,小Hi需要使得舰队的制空值不低于一个给定的值S,并且希望在这个条件下舰队的伤害值越高越好,这样能够尽量减少舰队的损耗。

同时,由于一艘舰船至少要装备一架对舰飞机才能够在炮击战中发动攻击,所以小Hi也好奇是否存在在满足制空值限制且伤害值最高的情况下,同时满足每一艘舰船至少装备一架对舰飞机。

而这个问题,就有待你来进行计算了~

输入

输入第一行为一个正整数Q,表示测试数据的组数。

在每组测试数据的第一行,为4个正整数N、M、T和S,意义如之前所述。

第2行~第n+1行,每行m个正整数,对应矩阵A

第n+2行,为T个正整数B1 .. BT

第n+3行,为T个正整数C1 .. CT

对于30%的数据,满足N<=2,M<=2,T<=20,Q<=100

对于剩下70%的数据,满足N<=4,M<=4,T<=1000,Q<=3

对于100%的数据,满足1<=Ai,j, Bi, Ci <= 1000,0<= S <= 108

输出

对于每组测试数据,如果存在满足制空值限制的方案的话,则首先在第一行输出在满足制空值限制下能够达到的最大攻击力D,在第二行中,如果在满足制空值限制且伤害值最高的情况下,能够同时满足每一艘舰船至少装备一架对舰飞机,则输出Yes,否则输出No。

如果不存在满足制空值限制的方案的话,则输出一行Not Exist。

样例输入
3
1 2 1 38
4 5 
0 
5
1 2 8 7
1 4 
0 3 2 0 0 2 0 0 
5 0 0 3 3 0 3 4 
2 1 4 29
5 
3 
0 4 3 0 
1 0 0 3
样例输出
Not Exist
5
Yes
0
No
一开始我想我一个两年的提督还搞不出这种题嘛就去怼了,然后发现还是需要一点技巧的。
思路如下(由于习惯,对空飞机称为舰战,对舰称为舰攻):
1.根据题目中描述的制空权和攻击值公式,我们很容易就能发现,要想最大化这两个值,就要把对空高或者攻击高的飞机放在大的装备栏里。所以我们需要分别对装备栏和飞机的参数升序排列。
2.由于不确定怎么放最好,而且装备栏数量m*n<=16,我们可以用二进制位表示每个格子放什么,从0到(2^(m*n))-1。然后数一下多少个舰战多少个舰攻,然后倒序往里面塞飞机,先塞对应机种数值大的。塞完为止。
3.航母在什么情况下不能攻击?题目中说的很明白是没有舰攻的时候。那么没有舰攻有几种可能呢?第一种当然是全是舰战;第二种则是在用二进制位判断的时候,本该放舰攻的格子因为舰攻放完了所以空着,此时航母也不能攻击。所以塞飞机时加个bool记录是否塞进去,然后在检验每个航母是否都能攻击时也注意看一下这个变量的值。
代码如下:
//hihocoder-hiho138
#include
#include
#include
#include
#include
#include
#define maxn 1005
#define maxm 1<<16;
using namespace std;
struct plane{
    int b,c;
    bool operator<(plane p) const{
        return (c>q;
    while(q--){
        cin>>n>>m>>t>>s;
        numb=numc=0;
        maxc=-1;
        int cnt=(1<<(n*m));
        int z=0;
        for(int i=0;i>amor[z].num;
                amor[z++].cv=i;
            }
        }
        for(int i=0;i>p[i].b;
            if(p[i].b>0)numb++;
        }
        for(int i=0;i>p[i].c;
            if(p[i].c>0)numc++;
        }
        sort(p,p+t);
        sort(amor,amor+n*m);
        for(int i=0;i>1;
            }
            tempc=min(n*m-tempb,numc);
            //cout<=0;j--){
                if(amor[j].kind==1){
                    if(temp_b==0)continue;
                    totalb+=p[--tempb].b*amor[j].num;
                    amor[j].has=true;
                    temp_b--;
                }
                else if(amor[j].kind==0){
                    if(tempc==0)continue;
                    totalc+=p[--temp].c*amor[j].num;
                    amor[j].has=true;
                    tempc--;
                }
            }
            if(totalb>=s&&totalc>=maxc){
                int ct[4]={0,0,0,0},flag=0;
                for(int j=0;jmaxc)all_attack_flag=0;
                }
                maxc=totalc;
            }
        }
        if(maxc==-1){
            cout<<"Not Exist"<

 

发表评论

电子邮件地址不会被公开。

This site uses Akismet to reduce spam. Learn how your comment data is processed.