[Offer收割]编程练习赛1 hihocoder 1271 舰队游戏 (状态压缩+贪心 好题)

本文主要是介绍[Offer收割]编程练习赛1 hihocoder 1271 舰队游戏 (状态压缩+贪心 好题),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

时间限制: 10000ms
单点时限: 1000ms
内存限制: 256MB

描述

小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

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


题目分析:这题现场ac的代码再交上去有一部分就wa了,不wa的有些也可以很轻松被hack。。。因为n和m很小,所以可以把状态压缩,用1表示放对空飞机,0表示放对舰飞机,对值直接从小到大排序,然后就是枚举状态贪心计算,要注意两点,算C的时候要把对应的状态记录下来,因为能放的位置排序完了后不一定都够放,有个剪枝,如果当前位置数大于飞机数了直接不用算了,因为当位置数小于等于飞机数的时候的状态都算过了,这是那种情况的子集,判断是否每个舰都有对舰飞机时,一定要与算C时的状态对应

另提供几组hack数据

2
4 4 4 20
5 5 5 5
1 1 1 1
1 1 1 1
1 1 1 1
0 2 2 0
5 0 0 1

4 3 3 5
6 8 3
4 8 6
6 6 1
1 1 5
1 0 0
0 10 10

答案:

30

No

160

No

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;
int const MAX = 1e3 + 5;
int n, m, t, s;
int sz_a, sz_b, sz_c;
int b[MAX], B[MAX], c[MAX], C[MAX];struct A
{int num, sta;
}a[5][5], tmp[20];bool cmp(A x, A y)
{return x.num > y.num;
}int cal_B(int sta)
{memset(tmp, 0, sizeof(tmp));sz_a = 0;for(int i = 0; i < n; i++)for(int j = 0; j < m; j++)if(sta & (1 << (i * m + j)))tmp[sz_a ++].num = a[i][j].num;sort(tmp, tmp + sz_a, cmp);int res = 0;for(int i = 0, j = 0; i < sz_a && j < sz_b; i++, j++)res += tmp[i].num * B[j];return res;
}int cal_C(int sta)
{   memset(tmp, 0, sizeof(tmp));sz_a = 0;for(int i = 0; i < n && sz_a <= sz_c; i++)for(int j = 0; j < m && sz_a <= sz_c; j++)if(!(sta & (1 << (i * m + j)))){tmp[sz_a].num = a[i][j].num;tmp[sz_a ++].sta = a[i][j].sta;   }sort(tmp, tmp + sz_a, cmp);int res = 0;for(int i = 0, j = 0; i < sz_a && j < sz_c; i++, j++)res += tmp[i].num * C[j];return res;
}bool Judge_C(int sta)
{for(int i = 0; i < n; i++){bool flag = false;for(int j = 0; j < m && !flag; j++)for(int k = 0; k < min(sz_a, sz_c) && !flag; k++)if(((1 << (i * m + j)) & tmp[k].sta))flag = true;if(!flag)return false;}return true;
}int main()
{int T;scanf("%d", &T);while(T --){sz_b = 0;sz_c = 0;scanf("%d %d %d %d", &n, &m, &t, &s);for(int i = 0; i < n; i++){for(int j = 0; j < m; j++){scanf("%d", &a[i][j].num);a[i][j].sta = (1 << (i * m + j));}}for(int i = 0; i < t; i++){scanf("%d", &b[i]);if(b[i])B[sz_b ++] = b[i];}for(int i = 0; i < t; i++){scanf("%d", &c[i]);if(c[i])C[sz_c ++] = c[i];}sort(B, B + sz_b, greater<int>());sort(C, C + sz_c, greater<int>());int ans = -1, tot = 1 << (n * m);bool hasC = false;for(int sta = 0; sta < tot; sta++){if(cal_B(sta) >= s){int maC = cal_C(sta);if(maC > ans || (maC == ans && !hasC)){ans = maC;hasC = Judge_C(sta);}}}if(ans == -1)printf("Not Exist\n");elseprintf("%d\n%s\n", ans, hasC ? "Yes" : "No");}
}

这篇关于[Offer收割]编程练习赛1 hihocoder 1271 舰队游戏 (状态压缩+贪心 好题)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/829615

相关文章

一文详解SpringBoot响应压缩功能的配置与优化

《一文详解SpringBoot响应压缩功能的配置与优化》SpringBoot的响应压缩功能基于智能协商机制,需同时满足很多条件,本文主要为大家详细介绍了SpringBoot响应压缩功能的配置与优化,需... 目录一、核心工作机制1.1 自动协商触发条件1.2 压缩处理流程二、配置方案详解2.1 基础YAML

Python实现将MySQL中所有表的数据都导出为CSV文件并压缩

《Python实现将MySQL中所有表的数据都导出为CSV文件并压缩》这篇文章主要为大家详细介绍了如何使用Python将MySQL数据库中所有表的数据都导出为CSV文件到一个目录,并压缩为zip文件到... python将mysql数据库中所有表的数据都导出为CSV文件到一个目录,并压缩为zip文件到另一个

Python异步编程中asyncio.gather的并发控制详解

《Python异步编程中asyncio.gather的并发控制详解》在Python异步编程生态中,asyncio.gather是并发任务调度的核心工具,本文将通过实际场景和代码示例,展示如何结合信号量... 目录一、asyncio.gather的原始行为解析二、信号量控制法:给并发装上"节流阀"三、进阶控制

Flutter监听当前页面可见与隐藏状态的代码详解

《Flutter监听当前页面可见与隐藏状态的代码详解》文章介绍了如何在Flutter中使用路由观察者来监听应用进入前台或后台状态以及页面的显示和隐藏,并通过代码示例讲解的非常详细,需要的朋友可以参考下... flutter 可以监听 app 进入前台还是后台状态,也可以监听当http://www.cppcn

MySQL 中的服务器配置和状态详解(MySQL Server Configuration and Status)

《MySQL中的服务器配置和状态详解(MySQLServerConfigurationandStatus)》MySQL服务器配置和状态设置包括服务器选项、系统变量和状态变量三个方面,可以通过... 目录mysql 之服务器配置和状态1 MySQL 架构和性能优化1.1 服务器配置和状态1.1.1 服务器选项

linux进程D状态的解决思路分享

《linux进程D状态的解决思路分享》在Linux系统中,进程在内核模式下等待I/O完成时会进入不间断睡眠状态(D状态),这种状态下,进程无法通过普通方式被杀死,本文通过实验模拟了这种状态,并分析了如... 目录1. 问题描述2. 问题分析3. 实验模拟3.1 使用losetup创建一个卷作为pv的磁盘3.

Python利用PIL进行图片压缩

《Python利用PIL进行图片压缩》有时在发送一些文件如PPT、Word时,由于文件中的图片太大,导致文件也太大,无法发送,所以本文为大家介绍了Python中图片压缩的方法,需要的可以参考下... 有时在发送一些文件如PPT、Word时,由于文件中的图片太大,导致文件也太大,无法发送,所有可以对文件中的图

Java实现状态模式的示例代码

《Java实现状态模式的示例代码》状态模式是一种行为型设计模式,允许对象根据其内部状态改变行为,本文主要介绍了Java实现状态模式的示例代码,文中通过示例代码介绍的非常详细,需要的朋友们下面随着小编来... 目录一、简介1、定义2、状态模式的结构二、Java实现案例1、电灯开关状态案例2、番茄工作法状态案例

通过prometheus监控Tomcat运行状态的操作流程

《通过prometheus监控Tomcat运行状态的操作流程》文章介绍了如何安装和配置Tomcat,并使用Prometheus和TomcatExporter来监控Tomcat的运行状态,文章详细讲解了... 目录Tomcat安装配置以及prometheus监控Tomcat一. 安装并配置tomcat1、安装

Linux之进程状态&&进程优先级详解

《Linux之进程状态&&进程优先级详解》文章介绍了操作系统中进程的状态,包括运行状态、阻塞状态和挂起状态,并详细解释了Linux下进程的具体状态及其管理,此外,文章还讨论了进程的优先级、查看和修改进... 目录一、操作系统的进程状态1.1运行状态1.2阻塞状态1.3挂起二、linux下具体的状态三、进程的