携程在线测试题答案
试题一：
乘积最大：
尝试不同的拆分方法，dp求解或者找规律
示例代码：
#include
#include
#include
#include
#define maxn 109
using namespace std;
long long dp[maxn][maxn];
int solve(int n){
long long ans = 0;
for(int i = 0; i <= n; i++)
ans = max(ans, dp[n][i]);
return ans;
}
int main(){
int n;
cin >> n;
for(int i = 0; i <= n; i++)
dp[0][i] = 1;
for(int i = 1; i <= n; i++){
for(int j = 1; j <= i; j++){
for(int k = 0 ; k < j; k++)
dp[i][j] = max(dp[i][j], dp[i - j][k] * j);
}
}
cout << solve(n) << endl;
return 0;
}
拼图：
经典问题，广度优先搜索
示例代码：
import java.io.*;
import java.util.*;
import java.text.*;
import java.math.*;
import java.util.regex.*;
import java.util.Scanner;
import java.util.Set;
import java.util.HashSet;
import java.util.ArrayList;
import java.lang.StringBuilder;
public class Main{
public static String destNumbers = "123456780";
public static Set set = new HashSet();
public static int[]moveTable = new int[]{12,14,10,13,15,11,5,7,3};
public static ArrayList getNextMoveList(Node pNode){
int position = pNode.numbers.indexOf("0");
int moveStatus = moveTable[position];
ArrayList cNodes = new ArrayList();
for(int status=1; status <=8; status=status<<1){
if((moveStatus & status) > 0){
char[] charNumbers = pNode.numbers.toCharArray();
int switchPosition = 0;
if(status == 1){
switchPosition = position - 3;
} else if(status == 2){
switchPosition = position - 1;
} else if(status == 4){
switchPosition = position + 1;
} else if(status == 8){
switchPosition = position + 3;
}
charNumbers[position] = charNumbers[switchPosition];
charNumbers[switchPosition] = '0';
String s = String.valueOf(charNumbers);
if(!set.contains(Integer.valueOf(s))){
set.add(Integer.valueOf(s));
Node n = new Node(pNode, s, charNumbers[position]);
cNodes.add(n);
}
}
}
return cNodes;
}
static int getResult(Node node){
String result = "";
while(node.parentNode != null){
result += node.currentNum;
node = node.parentNode;
}
return new StringBuffer(result).reverse().toString().length();
}
static int run(String numbers){
if(numbers.equals(destNumbers)){
return 0;
}
ArrayList numsList = new ArrayList();
numsList.add(new Node(null, numbers, ' '));
while(numsList.size() > 0){
ArrayList tmpList = new ArrayList();
for(Node pNode : numsList){
ArrayList cNodes = getNextMoveList(pNode);
for(Node cNode : cNodes){
if(cNode.numbers.equals(destNumbers)){
return getResult(cNode);
}
tmpList.add(cNode);
}
}
numsList = tmpList;
}
return -1;
}
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
String numbers = new String();
for(int rows=3; rows>0; rows--){
for(String n: scan.nextLine().split(" ")){
numbers += n;
}
}
int res = run(numbers);
System.out.println(String.valueOf(res));
}
}
class Node {
public Node(Node parentNode, String numbers, char currentNum){
this.numbers = numbers;
this.currentNum = currentNum;
this.parentNode = parentNode;
}
public char currentNum;
public String numbers;
public Node parentNode;
}
股票交易：
扫描序列，按照题意判断冷却时间，然后更新答案
示例代码：
#include
#include
#include
#include
using namespace std;
int a[1000006],dp[1000006];
int main(){
int n,k;
scanf("%d",&n);
for(int i=1;i<=n;i++) scanf("%d",&a[i]);
scanf("%d",&k);
int cur=-1000000000, ans=0;
for(int i=1;i<=n;i++)
{
dp[i]=max(a[i]+cur, dp[i-1]);
if(i>=k)
cur=max(cur, dp[i-k]-a[i]);
else
cur=max(cur, -a[i]);
ans=max(ans, dp[i]);
}
printf("%d\n",ans);
}