杭电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)的时候就把这个值记住,下一次遇到这个值就直接拿不需要再进行递归计算,这样就可以把时间复杂度降低。

ATCLOUD.NET-OVH海外高防云主机,采用KVM架构,稳定安全且便宜好用,仅3刀起

官方网站:点击访问ATCLOUD.NET官网优惠码:目前提供Cloud VPS与Storage VPS两款产品的六折优惠活动(续费同价,截止至2021年5月31日)优惠码:UMMBPBR20Z活动方案:一、型号CPU内存磁盘流量优惠价格购买链接VPS-1GB0.5×2.6+GHz1GB20GB1TB$3立即购买VPS-2GB1×2.6+GHz2GB50GB2TB$6立即购买VPS-4GB2×2.6...

新注册NameCheap账户几天后无法登录原因及解决办法

中午的时候有网友联系提到自己前几天看到Namecheap商家开学季促销活动期间有域名促销活动的,于是就信注册NC账户注册域名的。但是今天登录居然无法登录,这个问题比较困恼是不是商家跑路等问题。Namecheap商家跑路的可能性不大,前几天我还在他们家转移域名的。这里简单的记录我帮助他解决如何重新登录Namecheap商家的问题。1、检查邮件让他检查邮件是不是有官方的邮件提示。比如我们新注册账户是需...

VPSMS:53元/月KVM-512MB/15G SSD/1TB/洛杉矶CN2 GIA

VPSMS最近在做两周年活动,加上双十一也不久了,商家针对美国洛杉矶CN2 GIA线路VPS主机提供月付6.8折,季付6.2折优惠码,同时活动期间充值800元送150元。这是一家由港人和国人合资开办的VPS主机商,提供基于KVM架构的VPS主机,美国洛杉矶安畅的机器,线路方面电信联通CN2 GIA,移动直连,国内访问速度不错。下面分享几款VPS主机配置信息。CPU:1core内存:512MB硬盘:...

杭电acm为你推荐
公告格式通知格式范文校园网络拓扑图校园网络拓扑结构图点对点短信是什么国内点对点短信多少钱一条?制作证书怎么做证书?测量师QS工程师是测量师、造价师么?英文全称是什么?谁能帮忙解释一下,谢谢!软件更新不可用手机软件突然更新不了怎么办软件更新不可用为什么我用流量更新软件更新不了请问是什么原因????上海网络维护公司上海有没有专业公司网络维护的啊等保测评机构什么是三级等保体系 three-levelldap统一用户认证介绍H3CTE的H3CTE认证介绍
企业域名备案 唯品秀 buyvm vultr美国与日本 diahosting windows主机 godaddy优惠码 英语简历模板word 免费名片模板 轻博 绍兴高防 gspeed linux服务器维护 河南移动网 免费dns解析 网站在线扫描 环聊 www789 cxz 监控服务器 更多