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

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