携程在线测试题答案
试题一：
乘积最大：
尝试不同的拆分方法，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 .*;
import .*;
import .*;
import .*;
import x.*;
import ner;
import ;
import Set;
import yList;
import ngBuilder;
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 = xOf("0");
int moveStatus = moveTable[position];
ArrayList cNodes = new ArrayList();
for(int status=1; status <=8; status=status<<1){
if((moveStatus & status) > 0){
char[] charNumbers = arArray();
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 = eOf(charNumbers);
if(!ains(eOf(s))){
(eOf(s));
Node n = new Node(pNode, s, charNumbers[position]);
(n);
}
}
}
return cNodes;
}
static int getResult(Node node){
String result = "";
while(ntNode != null){
result += entNum;
node = ntNode;
}
return new StringBuffer(result)rse()ring()th();
}
static int run(String numbers){
if(ls(destNumbers)){
return 0;
}
ArrayList numsList = new ArrayList();
(new Node(null, numbers, ' '));
while(() > 0){
ArrayList tmpList = new ArrayList();
for(Node pNode : numsList){
ArrayList cNodes = getNextMoveList(pNode);
for(Node cNode : cNodes){
if(ls(destNumbers)){
return getResult(cNode);
}
(cNode);
}
}
numsList = tmpList;
}
return -1;
}
public static void main(String[] args) {
Scanner scan = new Scanner();
String numbers = new String();
for(int rows=3; rows>0; rows--){
for(String n: Line()t(" ")){
numbers += n;
}
}
int res = run(numbers);
tln(eOf(res));
}
}
class Node {
public Node(Node parentNode, String numbers, char currentNum){
ers = numbers;
entNum = currentNum;
ntNode = 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("%dn",ans);
}
