微软中国2020 OA

补充一下第三题 如果有人挑战一下智力极限
赛车问题 求最短时间 到达终点。n个城市 每个城市有自己的属性 Cop(直接淘汰) Sand(接下来两段路速度减半，在当前速度基础上) Nitro((接下来两段路速度加倍，在当前速度基础上) Crash(下一段路程耗时+一小时)
给了一个array of length n储存所有城市的属性
给了array of size [x][2] 每一行 [x][0]是一条路的起点城市[x][1]是这条路的终点城市 所以有x条路可以走
从一个城市出发 求到终点所需最短时间

Papaco 发表于 2020-3-25 16:23
哈哈哈哈哈哈心路历程和我一模一样！看到那道回文题还在暗喜碰到原题了，结果越写越不对orz

😢是一起跑偏的姐妹了

Jaye003 发表于 2020-3-25 17:08
因为时差弄错了时间没做😂
现在看来做了也白做😂

对的 我还吭哧吭哧六点多爬起来 人生不值得😊

第一个应该是幺四二 回文分割，战斗力这个题我能想到的是回溯，先把各组找出来，感觉不简单，加油加油，不过你这题目难度和隔壁完全是天壤之别啊，人家是公共子串，两数和。。。。。

kuboy 发表于 2020-3-27 03:39
第一个应该是幺四二 回文分割，战斗力这个题我能想到的是回溯，先把各组找出来，感觉不简单，加油加油，不 ...

天呐真的假的 我有看到有人题目和我是一模一样的 我觉得可能不是同一场考试 挠头）

区间DP？第一道题木

香槟小白菜 发表于 2020-3-26 11:11
补充一下第三题 如果有人挑战一下智力极限
赛车问题 求最短时间 到达终点。n个城市 每个城市有自己的属性  ...

只有记录两端顶点的邻接表，所以每个城市之间的路程标准耗时都是一小时？

第一道题 蠡口 burst ballons 先求出回文表，再用dp公式 dp[i][j] = isPalindrome[i][j] ? 1 : dp[i][k - 1] +dp[k +1][j] +1
第二道题 dp别想了，老老实实dfs暴力回溯。用dp的话将四个bit为1的mask收集为一个列表，然后用01背包整出最终结果，时间复杂度C(n, k)*(n / k)，肯定比回溯最优化剪枝要慢
第三道题感觉用dijkstra能做？

第一题是刷题网1246。hard，很棒。