携程在线测试题答案

经典word整理文档，仅参考，双击此处可删除页眉页脚。本资料属于网络整理，如有侵权，请联系删除，谢谢！乘积最大：尝试不同的拆分方法，dp求解或者找规律例如代码：#include#include#include#include#definemaxn109usingnamespacestd;longlongdp[maxn][maxn];intsolve(intn){longlongans=0;for(inti=0;i<=n;i++)ans=max(ans,dp[n][i]);returnans;}intmain(){intn;cin>>n;for(inti=0;i<=n;i++)dp[0][i]=1;for(inti=1;i<=n;i++){for(intj=1;j<=i;j++){for(intk=0;k<j;k++)dp[i][j]=max(dp[i][j],dp[i-j][k]*j);}}cout<<solve(n)<<endl;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="123456780";publicstaticSetset=newHashSet();publicstaticint[]moveTable=newint[]{12,14,10,13,15,11,5,7,3};publicstaticArrayListgetNextMoveList(NodepNode){intposition=pNode.numbers.indexOf("0");intmoveStatus=moveTable[position];ArrayListcNodes=newArrayList();for(intstatus=1;status<=8;status=status<<1){if((moveStatus&status)>0){char[]charNumbers=pNode.numbers.toCharArray();intswitchPosition=0;if(status==1){switchPosition=position-3;}elseif(status==2){switchPosition=position-1;}elseif(status==4){switchPosition=position+1;}elseif(status==8){switchPosition=position+3;}charNumbers[position]=charNumbers[switchPosition];charNumbers[switchPosition]='0';Strings=String.valueOf(charNumbers);if(!set.contains(Integer.valueOf(s))){set.add(Integer.valueOf(s));Noden=newNode(pNode,s,charNumbers[position]);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;}return-1;}publicstaticvoidmain(String[]args){Scannerscan=newScanner(System.in);Stringnumbers=newString();for(introws=3;rows>0;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#includeusingnamespacestd;inta[1000006],dp[1000006];intmain(){intn,k;scanf("%d",&n);for(inti=1;i<=n;i++)scanf("%d",&a[i]);scanf("%d",&k);intcur=-1000000000