携程在线测试题答案.doc

携程在线测试题答案 试题一： 乘积最大： 尝试不同的拆分方法dp求解或者找规律 示例代码： include include include include definemaxn109 usingnamespacestd; longlongdpmaxnmaxn; intsolve(intn) longlongans=0; for(inti=0;in; for(inti=0;i=n;i+) dp0i=1; for(inti=1;i=n;i+) for(intj=1;j=i;j+) for(intk=0;k dpij=max(dpij,dpijk*j); cout return0; 拼图： 经典问题广度优先搜索 示例代码： importjava.io.*; importjava.util.*; importjava.text.*; importjava.math.*; importjava.util.regex.*; importjava.util.Scanner; importjava.util.Set; importjava.util.HashSet; importjava.util.ArrayList; importjava.lang.StringBuilder; publicclassMain publicstaticStringdestNumbers=432156780; publicstaticSetset=newHashSet(); publicstaticintmoveTable=newint12,14,10,13,15,11,5,7,3; publicstaticArrayListgetNextMoveList(NodepNode) intposition=pNode.numbers.indexOf(0); intmoveStatus=moveTableposition; ArrayListcNodes=newArrayList(); for(intstatus=1;status=8;status=status0) charcharNumbers=pNode.numbers.toCharArray(); intswitchPosition=0; if(status=1) switchPosition=position3; elseif(status=2) switchPosition=position1; elseif(status=4) switchPosition=position+1; elseif(status=8) switchPosition=position+3; charNumbersposition=charNumbersswitchPosition; charNumbersswitchPosition=0; Strings=String.valueOf(charNumbers); if(set.contains(Integer.valueOf(s) set.add(Integer.valueOf(s); Noden=newNode(pNode,s,charNumbersposition); cNodes.add(n); returncNodes; staticintgetResult(Nodenode) Stringresult=; while(node.parentNode=null) result+=node.currentNum; node=node.parentNode; returnnewStringBuffer(result).reverse().toString().length(); staticintrun(Stringnumbers) if(numbers.equals(destNumbers) return0; ArrayListnumsList=newArrayList(); numsList.add(newNode(null,numbers,); while(numsList.size()0) ArrayListtmpList=newArrayList(); for(NodepNode:numsList) ArrayListcNodes=getNextMoveList(pNode); for(NodecNode:cNodes) if(cNode.numbers.equals(destNumbers) returngetResult(cNode); tmpList.add(cNode); numsList=tmpList; return1; publicstaticvoidmain(Stringargs) Scannerscan=newScanner(System.in); Stringnumbers=newString(); for(introws=3;rows0;rows) for(Stringn:scan.nextLine().split() numbers+=n; intres=run(numbers); System.out.println(String.valueOf(res); classNode publicNode(NodeparentNode,Stringnumbers,charcurrentNum) this.numbers=numbers; this.currentNum=currentNum; this.parentNode=parentNode; publiccharcurrentNum; publicStringnumbers; publicNodeparentNode; 股票交易： 扫描序列按照题意判断冷却时间然后更新答案 示例代码： include include include include usingnamespacestd; inta1000006,dp1000006; intmain() intn,k; scanf(%d,n); for(inti=1;i=n;i+)scanf(%d,ai);