[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使用GZIP压缩反回数据问题

《SpringBoot使用GZIP压缩反回数据问题》:本文主要介绍SpringBoot使用GZIP压缩反回数据问题,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录SpringBoot使用GZIP压缩反回数据1、初识gzip2、gzip是什么,可以干什么?3、Spr

shell编程之函数与数组的使用详解

《shell编程之函数与数组的使用详解》:本文主要介绍shell编程之函数与数组的使用,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录shell函数函数的用法俩个数求和系统资源监控并报警函数函数变量的作用范围函数的参数递归函数shell数组获取数组的长度读取某下的

SpringSecurity JWT基于令牌的无状态认证实现

《SpringSecurityJWT基于令牌的无状态认证实现》SpringSecurity中实现基于JWT的无状态认证是一种常见的做法,本文就来介绍一下SpringSecurityJWT基于令牌的无... 目录引言一、JWT基本原理与结构二、Spring Security JWT依赖配置三、JWT令牌生成与

Java图片压缩三种高效压缩方案详细解析

《Java图片压缩三种高效压缩方案详细解析》图片压缩通常涉及减少图片的尺寸缩放、调整图片的质量(针对JPEG、PNG等)、使用特定的算法来减少图片的数据量等,:本文主要介绍Java图片压缩三种高效... 目录一、基于OpenCV的智能尺寸压缩技术亮点:适用场景:二、JPEG质量参数压缩关键技术:压缩效果对比

关于WebSocket协议状态码解析

《关于WebSocket协议状态码解析》:本文主要介绍关于WebSocket协议状态码的使用方式,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录WebSocket协议状态码解析1. 引言2. WebSocket协议状态码概述3. WebSocket协议状态码详解3

SpringBoot3实现Gzip压缩优化的技术指南

《SpringBoot3实现Gzip压缩优化的技术指南》随着Web应用的用户量和数据量增加,网络带宽和页面加载速度逐渐成为瓶颈,为了减少数据传输量,提高用户体验,我们可以使用Gzip压缩HTTP响应,... 目录1、简述2、配置2.1 添加依赖2.2 配置 Gzip 压缩3、服务端应用4、前端应用4.1 N

揭秘Python Socket网络编程的7种硬核用法

《揭秘PythonSocket网络编程的7种硬核用法》Socket不仅能做聊天室,还能干一大堆硬核操作,这篇文章就带大家看看Python网络编程的7种超实用玩法,感兴趣的小伙伴可以跟随小编一起... 目录1.端口扫描器:探测开放端口2.简易 HTTP 服务器:10 秒搭个网页3.局域网游戏:多人联机对战4.

Java并发编程必备之Synchronized关键字深入解析

《Java并发编程必备之Synchronized关键字深入解析》本文我们深入探索了Java中的Synchronized关键字,包括其互斥性和可重入性的特性,文章详细介绍了Synchronized的三种... 目录一、前言二、Synchronized关键字2.1 Synchronized的特性1. 互斥2.

一文详解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文件到另一个