杭电acm杭电ACM 2044题 为什么总是超时

杭电acm  时间:2021-08-21  阅读:()

杭电ACM 1011,能不能讲讲题目究竟是什么意思,到底该怎样分配部队?感谢大神!

就是说某个国家(Starship)有很多贪官(brains),他们在一些房间聚会,房间配置了一些保镖(bugs),作为反贪部队的队长你需要指挥部队(Troopers)去活捉贪官,(只有活捉才能追回赃款~(≧▽≦)/~啦啦啦),现在问题是留下一个小分队只能对付20个保镖,所以要利益最大化,需要合理配置每个房间的分队数,尽量多的活捉,其他的放毒气干掉;又因为他们聚会的房子连在一起,所以部队行进路线不能返回同一个房间(避免他们通风报信?)。

几个小提示, 1。

当一个房间无保镖有贪官,如果是中途路过的房间,就不需要留下小分队,否则就需要一个。

2。

N个房间N-1个连通门,说明是单连通的,所以要确定进攻路线 3。

就算计算好的最佳进攻路线中有些房间有贪官,有时也需要放弃,为了活捉最多 4。

下面的代码没有AC,有时错误,有时超时,因为是java写的?容易超时。

但一些基本的数据测试通过了;如果你用C,应该好优化 import java.util.ArrayList; import java.util.List; import java.util.Scanner; /** * for 杭电 ACM1011 * @author 718225250 * for more see * /qq718225250/article/details/8764380 */ public class Main{ public static class Cavern{ Integer id; int bugs; int brains; int troopers; boolean isPass = false;//是否已经过 List<Integer> next = new ArrayList<Integer>(); public Cavern(int id, int bugs, int brains){ this.id = Integer.valueOf(id); this.bugs = bugs; this.brains = brains; this.troopers = (bugs%20==0 ? bugs/20 : bugs/20+1); } } /** * 获得一次遍历的最大值 * @return */ public static int getMax(){ int Max =curMax; int id = _list.get(_list.size()-1); boolean hasNextForPass = false;/*是否还有下一个节点供遍历*/ for(int i=0;i< _caverns[id].next.size();i++){ Integer nextId = _caverns[id].next.get(i); if(!_caverns[nextId].isPass){ hasNextForPass = true; _list.add(nextId); _caverns[nextId].isPass = true; Max = getMax(); _caverns[nextId].isPass = false; _list.remove(_list.size()-1); } } if(!hasNextForPass){ int tempMax = getResult() ; if(tempMax > Max){ curMax = tempMax; Max = curMax; } } return Max; } /** * 获得结果 * @return */ public static int getResult(){ int result = 0; int tempTrooperNumber = __TrooperNumber; int tempResult = 0; boolean flag = true; for(int i =0; i < _list.size(); i++ ){ Integer id = _list.get(i); if(tempTrooperNumber >= _caverns[id].troopers){ tempTrooperNumber -= _caverns[id].troopers; tempResult += _caverns[id].brains; } else{ flag = false; break; } } if(flag){ result = tempResult; }else{ tempResult = 0; for(int i =0; i < _list.size(); i++ ){ Integer id = _list.get(i); _list.remove(id); tempResult = getResult(); if(tempResult > result){ result = tempResult; } _list.add(id); } } return result; } public static int __CavernNumber; public static int __TrooperNumber; public static Cavern[] _caverns; public static int curMax; public static final List<Integer> _list = new ArrayList<Integer>(); public static void main(String[] args){ Scanner in=new Scanner(System.in); while(true){ __CavernNumber = in.nextInt(); __TrooperNumber = in.nextInt(); if( __CavernNumber < 0 && __TrooperNumber < 0 ){ break; } else if(__CavernNumber == 0 || __TrooperNumber == 0){ System.out.println(0); } else{ _caverns = new Cavern[__CavernNumber]; for(int i=0;i<__CavernNumber;i++){ int bugs = in.nextInt(); int brains = in.nextInt(); _caverns[i] = new Cavern(i, bugs, brains); } for(int i=0;i<__CavernNumber-1;i++){ int m = in.nextInt(); int n = in.nextInt(); _caverns[m-1].next.add(n-1); _caverns[n-1].next.add(m-1); } curMax = 0; Integer start = Integer.valueOf(0); _caverns[0].isPass = true; _list.add(start); System.out.println(getMax()); } } } }

杭电ACM 1004,1005,1006,这三题是的意思是什么

我只说大概的意思。

能让你知道怎么做题。

1004:题意:结合数据的输入,给你N个汽球,接着给出这N个汽球的颜色,统计出现颜色最多的那个汽球并输出相对应的汽球颜色。

输入有多组。

以汽球个数N为0时结束输入。

1005:这题就一个数学公式的描述,就是输入三个数:A,B,n, 求当f(1) = 1, f(2) = 1, f(n) = (A * f(n - 1) + B * f(n - 2)) mod 7.时,求对应的f(n)的值。

输入有多组。

以输入三个0 0 0时,结束输入。

1006:多组输入一个D(0<=D <= 120),以及-1结束输入。

求时钟一天时,分,秒,三根针两两的角度至少为D的时间总和占一天时间的百分之几。

结果保留三位小数。

杭电ACM 2044题 为什么总是超时

你的递归扩展起来很可怕。

因为有很多是重复算的,例如: F(5) / F(4) F(3) / F(3) F(2) 在这里F(3)就要算两遍,这题需要把这种情况给解决,也就是说可以将递归改成递推,也可以用记忆化搜索的方法解决,也就是算第一遍mf(a,n)的时候就把这个值记住,下一次遇到这个值就直接拿不需要再进行递归计算,这样就可以把时间复杂度降低。

Ceraus24元/月,国庆促销 香港云上新首月五折

Ceraus数据成立于2020年底,基于KVM虚拟架构技术;主营提供香港CN2、美国洛杉矶CN2、日本CN2的相关VPS云主机业务。喜迎国庆香港上新首月五折不限新老用户,cera机房,线路好,机器稳,适合做站五折优惠码:gqceraus 续费七五折官方网站:https://www.ceraus.com香港云内存​CPU硬盘流量宽带优惠价格购买地址香港云2G2核40G不限5Mbps24元/月点击购买...

wordpress投资主题模版 白银黄金贵金属金融投资网站主题

wordpress投资主题模版是一套适合白银、黄金、贵金属投资网站主题模板,绿色大气金融投资类网站主题,专业高级自适应多设备企业CMS建站主题 完善的外贸企业建站功能模块 + 高效通用的后台自定义设置,简洁大气的网站风格设计 + 更利于SEO搜索优化和站点收录排名!点击进入:wordpress投资主题模版安装环境:运行环境:PHP 7.0+, MYSQL 5.6 ( 最低主机需求 )最新兼容:完美...

ZJI:香港物理服务器,2*E5-2630L/32G/480G SSD/30Mbps/2IP/香港BGP,月付520元

zji怎么样?zji是一家老牌国人主机商家,公司开办在香港,这个平台主要销售独立服务器业务,和hostkvm是同一样,两个平台销售的产品类别不一平,商家的技术非常不错,机器非常稳定。昨天收到商家的优惠推送,目前针对香港邦联四型推出了65折优惠BGP线路服务器,性价比非常不错,有需要香港独立服务器的朋友可以入手,非常适合做站。zji优惠码:月付/年付优惠码:zji 物理服务器/VDS/虚拟主机空间订...

杭电acm为你推荐
显示系统电脑开机显示系统错误怎么办零终端银行卡圈存是什么意思查看加密空间怎么看加密的qq空间网络黑科技什么防封软件,都是假的,没有一个是真的,大家不要受骗!信息发布管理系统信息发布系统属于建筑智能工程哪个分部access数据库入门access的用法?宽带包月宽带可以按月办吗终端设备什么是终端设备生产商?伙伴云毒霸中的云安全指的是什么意思?usingc++中的using namespace std有什么作用?
网通vps 科迈动态域名 七牛优惠码 80vps 便宜建站 directadmin 香港新世界电讯 安徽双线服务器 申请网站 国外免费网盘 hosting24 建站论坛 windowsserver2012 美国vpn服务器 日本小学生 let 最好的空间留言 西部数码空间购买 视频监控服务器 个人web服务器 更多