🐶 昂赛 + match 后还是没过HC

yiliaobailiao 发表于 2021-11-18 14:35
一维不够吧？至少需要知道上一圈用了哪种轮胎，以及是那条轮胎被使用的第几圈？

我补充里贴了一个大神的思路，我和他的思路差不多，你可以看眼，可以讨论下。

yulisa1 发表于 2021-11-18 01:27
可以麻烦楼主分享下轮胎那题1维Dp的写法吗  因为有N中轮胎 所以要记录目前最优，还要记录上一轮是哪个轮胎 ...

我主贴里面补充了一个大神的思路，你可以看眼

Neo333 发表于 2021-11-17 21:54
楼主，第四题感觉一维数组转换方程写不出来啊...

我补充里贴了一个大神的思路，我和他的思路差不多，你可以看眼，可以讨论下。

Dionysus的酒 发表于 2021-11-17 17:52
楼主心态和思维都很好 有这些经验就算狗家拒了也一定会有好offer的！

谢谢安慰，呜呜呜，你真是好人。

匿名者 发表于 2021-11-16 20:14
和这个面筋的第一题一样的 https://www.1point3acres.com/bbs/thread-795024-1-1.html

看了下 还真是一模一样

第四题的解法不对。

“第四题是DP，有N种轮胎，每种轮胎有连个参数T和F，T是用这种轮胎跑第一圈需要的秒数，F是轮胎的磨损程度，每跑一圈，下一圈如果不换轮胎的话，那就得花T*F秒，也就是比如跑10圈不换轮胎的话，总时间是T + T*F + T* F^2 + ..... T * F^9。现在每种轮胎不限量供应，每一圈可以换轮胎也可以不换，换轮胎花费P秒，问你跑K圈需要花费的最小圈数。面试官很耐心的给我hints，太感谢了。”

总共N种轮胎， 每种的T_n, F_n 都不一样。 解法里没有体现出多种轮胎。这个解法只适用于N=1。
working的解法1：
dp(k, c) is the min_time in the preffix laps[:k+1] which ends with tire c.
Iterate over the rightmost chunk of repetative tires r in range(k) and iterate over the tire preceding the the chunk which is different.
dp(k, c) = min(chunk(c, r) + p + dp(k-r, cp) for r in range(1, k+1) for cp != c)
Base: dp(0, c) = 0
Return: min(dp(N, c))

Complexity:
T = O(V=N*C) + O(E=C*N*(C-1) * N)

更优的解法：
dp(k, c, r) is the min_timecost in the suffix laps[k:], when the previous tire is c and has been contiguously used which ends at the r-th element in the identical seq.
t[c]*f[c]**r
t[cp]*f[cp]**0 + q

dp(k, c, r) = min(t[c]*f[c]**(r+1) + dp(k+1, c, r+1), q + t[cp]*f[cp]**0 + dp(k+1, cp, 0) for cp != c)

Base: dp(N, all c, all r) = 0
Return: min(dp(0, c, 0) for c in range(C))

Time complexity:
O(V = N*C*N) + O(E)
E = C*C*N

lxy16555 发表于 2021-11-18 21:20
2. DP+二分，dp[k]表示第k位置可接受的最小值，返回dp填坑的长度
3. 取出所有房子坐标，dfs+backtracking ...

第四题的解法有点问题。层主只考虑了一种轮胎。其实是有N种轮胎。

yiliaobailiao 发表于 2021-12-18 20:38:03
第四题的解法有点问题。层主只考虑了一种轮胎。其实是有N种轮胎。

没有问题，换胎的时间和圈在中间的转换方程里都体现了，j是个loop 0～i

lxy16555 发表于 2021-12-19 00:24
没有问题，换胎的时间和圈在中间的转换方程里都体现了，j是个loop 0～i

明白了。多谢回复。不同种类的轮胎，在计算一直不换轮胎的时候用到了。一旦某个时间换了轮胎，那么前后两个子问题，就完全是独立的了。

我晕 为啥我都没有team match 呢。 我给hr 说 我自己能找到组要我。hr 也不理我 说直接把我的package 送去 final discussion。。。。无语啊