r*********n
发帖数: 4553 | 1 分披萨：你选一块，然后对手拿走左右各一块，一直重复直到分完整个披萨。找一个方
法，使得你得到的披萨最多。
抽象起来就是一组正整数数组，比如[2, 4, 8, 1, 3, 10]。
第一次选10， 对手拿走2，3 （注意数组是circular的）
第二次选8，对手拿走4，1
使得你得到的正整数和最大
还问两道常见的算法题，答得很轻松，又问了我的研究课题。最后出了这么一道题，面
馆说他刚看到一道题，他没想出来，于是问我的想法。我也没想出来，就给了一个笨方
法，然后分析了一下复杂度。
然后recruiter就玩失踪，大概是被G磨具了。
PS: 面馆是一三个，大家聊得还挺投机的，最后还是悲剧，这可能就是所谓的笑里藏刀
了。 |
N*D
发帖数: 3641 | |
G****A
发帖数: 4160 | 3 G家现在的hire策略有点怪:题目容易，bar很高。
难道最终HC坐在一起看学校排名？
【在 r*********n 的大作中提到】
: 分披萨：你选一块，然后对手拿走左右各一块，一直重复直到分完整个披萨。找一个方
: 法，使得你得到的披萨最多。
: 抽象起来就是一组正整数数组，比如[2, 4, 8, 1, 3, 10]。
: 第一次选10， 对手拿走2，3 （注意数组是circular的）
: 第二次选8，对手拿走4，1
: 使得你得到的正整数和最大
: 还问两道常见的算法题，答得很轻松，又问了我的研究课题。最后出了这么一道题，面
: 馆说他刚看到一道题，他没想出来，于是问我的想法。我也没想出来，就给了一个笨方
: 法，然后分析了一下复杂度。
: 然后recruiter就玩失踪，大概是被G磨具了。
|
f*******t
发帖数: 7549 | 4 这题是典型的DP吧
DP[i][j] = MAX(A[i] + DP[i+2][j-1], A[j] + DP[i+1][j-2]) |
x*********w
发帖数: 533 | 5
电锯惊魂啊
【在 N*D 的大作中提到】
: 狗狗一般不会磨具吧，都是电锯
|
r*********n
发帖数: 4553 | 6 应该是用DP解，复杂度应该是O(n^2)，但是你这个optimal structure不对吧，因为数
组是circular的，而且不一定要从两端开始选。
【在 f*******t 的大作中提到】
: 这题是典型的DP吧
: DP[i][j] = MAX(A[i] + DP[i+2][j-1], A[j] + DP[i+1][j-2])
|
f*******t
发帖数: 7549 | 7 circular的话感觉复杂度比n^2高
【在 r*********n 的大作中提到】
: 应该是用DP解，复杂度应该是O(n^2)，但是你这个optimal structure不对吧，因为数
: 组是circular的，而且不一定要从两端开始选。
|
r*********n
发帖数: 4553 | 8 面馆给我说有一个O(n^2)算法，但他自己还没想出来........
【在 f*******t 的大作中提到】
: circular的话感觉复杂度比n^2高
|
f*******t
发帖数: 7549 | 9 呃，这题估计是ACM中等难度题，我反正是无能为力了
【在 r*********n 的大作中提到】
: 面馆给我说有一个O(n^2)算法，但他自己还没想出来........
|
w**********o
发帖数: 140 | |
|
|
p******9
发帖数: 47 | 11 这题可以转化成 在N个数的环形数组中取不相邻的N/3(上取整)，使这些数和最大。我
们可以证明任意这N/3个不相邻的数，必然能对应一种符合原题的取法。
可以用数学归纳法证明这个问题，为了方便，重新定义一下变量名，另M为我会取得到
的比萨数，则N有三种情况，即N=3M - 2 , N = 3M - 1, N = 3M，我们只证明N = 3M -
2这种情况，因为这个时候若能取到，N= 3M - 1或N = 3M 的时候肯定能取到。
（1）基础条件：若M <= 3，我们可以枚举证明以上命题成立。
（2）假设M的时候成立，我们证明M + 1的时候也成立。在M + 1的时候，将会有N = 3
(M + 1) - 2= 3M + 1块比萨。而此时M + 1块比萨之间互不相邻，则在这M + 1块比萨
间将会有M + 2个槽（考虑到比萨时环形的），我们将剩余的2M块比萨放到这M + 2个槽
里，因为M >=3，基于鸽笼原理，必定会有两个比萨落到这个槽里。此时整个序列的形
状如下所示：...PXPXXP... 。我们取定中间的那个P，则对手取定旁边的两个X，形状
变成...PXP...。这个时候问题变退化成了M的情况，并保证这M块比萨依然互不相邻。
由于M的时候问题成立，则M+1的时候问题也成立。
进一步的，我们知道N = 3M - 1 , N = 3M的时候问题也成立，从而整个命题成立。
进一步的，这个问题需要从环形数组转化成非环形数组的情况，对取不取第一个数做讨
论，如果取第一个数，则问题变成从前N-1个数取N/3个数，如果不取，问题变成从后N-
1个数取N/3个数。
对于非环形数组的话，这个问题可以用DP来解，dp[N][K]表示从前N个数取K个数的最大
值。那么dp[N][K] = max(dp[N - 1][K] , dp[N - 2][k - 1] + pizza[N])。前者表
示不取第N块比萨，后者表示取第N块比萨。最后问题的解便是 dp[N][ceiling(N/3)]。
这样下来，整个问题是O(n^2)的复杂度，编程应该很容易实现，欢迎指证错误。 |
f*******t
发帖数: 7549 | 12 某牛想出一种greedy解：
每次取与两边差最大的数
目前没想出反例，但也不会证明，谁能判断下对错 |
d**********x
发帖数: 4083 | 13 这个我想过了，是错的
1 5 1 4 1 1 4
绕一圈，然后按照greedy算法应该是先拿5，但是实际上应该先拿两个4，最后剩下一个
5，拿走。
【在 f*******t 的大作中提到】
: 某牛想出一种greedy解：
: 每次取与两边差最大的数
: 目前没想出反例，但也不会证明，谁能判断下对错
|
x*****0
发帖数: 452 | |
n*****i
发帖数: 64 | 15 配合alpha-beta pruning??虽然是ai的基本算法，但是作为面试题还是变态了点吧？？
【在 w**********o 的大作中提到】
: Try Minimax tree
|
n*****i
发帖数: 64 | 16 这个递归想法nb
3
/3
【在 p******9 的大作中提到】
: 这题可以转化成 在N个数的环形数组中取不相邻的N/3(上取整)，使这些数和最大。我
: 们可以证明任意这N/3个不相邻的数，必然能对应一种符合原题的取法。
: 可以用数学归纳法证明这个问题，为了方便，重新定义一下变量名，另M为我会取得到
: 的比萨数，则N有三种情况，即N=3M - 2 , N = 3M - 1, N = 3M，我们只证明N = 3M -
: 2这种情况，因为这个时候若能取到，N= 3M - 1或N = 3M 的时候肯定能取到。
: （1）基础条件：若M <= 3，我们可以枚举证明以上命题成立。
: （2）假设M的时候成立，我们证明M + 1的时候也成立。在M + 1的时候，将会有N = 3
: (M + 1) - 2= 3M + 1块比萨。而此时M + 1块比萨之间互不相邻，则在这M + 1块比萨
: 间将会有M + 2个槽（考虑到比萨时环形的），我们将剩余的2M块比萨放到这M + 2个槽
: 里，因为M >=3，基于鸽笼原理，必定会有两个比萨落到这个槽里。此时整个序列的形
|
c********t
发帖数: 5706 | 17 如果从dp考虑，这道题比分金币难不少啊，光写 f(i,j) 与f(i-1, j+1)转移方程好像
不行，因为i or j可能已经早被选走，想不出。
能不能用greedy?
【在 r*********n 的大作中提到】
: 分披萨：你选一块，然后对手拿走左右各一块，一直重复直到分完整个披萨。找一个方
: 法，使得你得到的披萨最多。
: 抽象起来就是一组正整数数组，比如[2, 4, 8, 1, 3, 10]。
: 第一次选10， 对手拿走2，3 （注意数组是circular的）
: 第二次选8，对手拿走4，1
: 使得你得到的正整数和最大
: 还问两道常见的算法题，答得很轻松，又问了我的研究课题。最后出了这么一道题，面
: 馆说他刚看到一道题，他没想出来，于是问我的想法。我也没想出来，就给了一个笨方
: 法，然后分析了一下复杂度。
: 然后recruiter就玩失踪，大概是被G磨具了。
|
c********t
发帖数: 5706 | 18 取与两边差值最大的数，应该先取两个4. 我觉得这个greedy算法可行。不过不知怎么
证明。
(4-（1+1)) > (5-(1+4))
【在 d**********x 的大作中提到】
: 这个我想过了，是错的
: 1 5 1 4 1 1 4
: 绕一圈，然后按照greedy算法应该是先拿5，但是实际上应该先拿两个4，最后剩下一个
: 5，拿走。
|
d**********x
发帖数: 4083 | 19 啥？
5的两边是两个1啊
一个
【在 c********t 的大作中提到】
: 取与两边差值最大的数，应该先取两个4. 我觉得这个greedy算法可行。不过不知怎么
: 证明。
: (4-（1+1)) > (5-(1+4))
|
c********t
发帖数: 5706 | 20 哦，眼神不好。看来是不行啊。
【在 d**********x 的大作中提到】
: 啥？
: 5的两边是两个1啊
:
: 一个
|
|
|
c********t
发帖数: 5706 | 21 发现没理解题目。
请问对于 3,1,6,1,4,2
第一轮 拿走 6,1,1后
第二轮 A拿走4的时候, 这时候3算相邻的吗？
【在 r*********n 的大作中提到】
: 分披萨：你选一块，然后对手拿走左右各一块，一直重复直到分完整个披萨。找一个方
: 法，使得你得到的披萨最多。
: 抽象起来就是一组正整数数组，比如[2, 4, 8, 1, 3, 10]。
: 第一次选10， 对手拿走2，3 （注意数组是circular的）
: 第二次选8，对手拿走4，1
: 使得你得到的正整数和最大
: 还问两道常见的算法题，答得很轻松，又问了我的研究课题。最后出了这么一道题，面
: 馆说他刚看到一道题，他没想出来，于是问我的想法。我也没想出来，就给了一个笨方
: 法，然后分析了一下复杂度。
: 然后recruiter就玩失踪，大概是被G磨具了。
|
r*********n
发帖数: 4553 | 22 你拿6，对手拿1,1, 剩下[3,4,2]
然后你拿4，对手拿3,2
用传统的dp[i,j]来解这到题，遇到的问题是dp[i,j]（i<=j）不能由dp[k,l]（k>=i, l
<=j, k <=l）来决定, 因为index是循环的。
【在 c********t 的大作中提到】
: 发现没理解题目。
: 请问对于 3,1,6,1,4,2
: 第一轮 拿走 6,1,1后
: 第二轮 A拿走4的时候, 这时候3算相邻的吗？
|
j*****y
发帖数: 1071 | 23 那哥们不是需要 brute force 吧？ 呵呵
l
【在 r*********n 的大作中提到】
: 你拿6，对手拿1,1, 剩下[3,4,2]
: 然后你拿4，对手拿3,2
: 用传统的dp[i,j]来解这到题，遇到的问题是dp[i,j]（i<=j）不能由dp[k,l]（k>=i, l
: <=j, k <=l）来决定, 因为index是循环的。
|
c********t
发帖数: 5706 | 24 明白了。 那就找到不相邻的 (N+2)/3 个元素,使sum最大。需要证明只要不相邻，一定
都能取到。
l
【在 r*********n 的大作中提到】
: 你拿6，对手拿1,1, 剩下[3,4,2]
: 然后你拿4，对手拿3,2
: 用传统的dp[i,j]来解这到题，遇到的问题是dp[i,j]（i<=j）不能由dp[k,l]（k>=i, l
: <=j, k <=l）来决定, 因为index是循环的。
|
r*********n
发帖数: 4553 | 25 我说了brute force的算法，当时为了争取时间，一边说bf方法，一边分析复杂度，一
边想dp。这题一共花了10min不到，我觉得如果没见过这题，想要在10min之内解出来不
是科班出生的基本不太现实吧。
【在 j*****y 的大作中提到】
: 那哥们不是需要 brute force 吧？ 呵呵
:
: l
|
j*****y
发帖数: 1071 | 26 你是怎么做的阿? 学习一下
【在 r*********n 的大作中提到】
: 我说了brute force的算法，当时为了争取时间，一边说bf方法，一边分析复杂度，一
: 边想dp。这题一共花了10min不到，我觉得如果没见过这题，想要在10min之内解出来不
: 是科班出生的基本不太现实吧。
|
r*********n
发帖数: 4553 | 27 就像求permutation一样，一路dfs下去，取走之后mark一下，唯一要注意的是index是
循环的，复杂度是n factorial
【在 j*****y 的大作中提到】
: 你是怎么做的阿? 学习一下
|
j*****y
发帖数: 1071 | 28 那还是 brute force 阿？
【在 r*********n 的大作中提到】
: 就像求permutation一样，一路dfs下去，取走之后mark一下，唯一要注意的是index是
: 循环的，复杂度是n factorial
|
y***g
发帖数: 1492 | 29 不相邻也不一定能取道
明白了。 那就找到不相邻的 (N 2)/3 个元素,使sum最大。需要证明只要不相邻，一定
都能取到。
【在 c********t 的大作中提到】
: 明白了。 那就找到不相邻的 (N+2)/3 个元素,使sum最大。需要证明只要不相邻，一定
: 都能取到。
:
: l
|
r*********n
发帖数: 4553 | 30 对啊，所以说是笨方法嘛....
【在 j*****y 的大作中提到】
: 那还是 brute force 阿？
|
|
|
f*********m
发帖数: 726 | 31 brute force+look up table（去掉重复）？ |
j********x
发帖数: 2330 | 32 似乎是取ceil(n / 3)个数，每两个数之间至少间隔1个元素，并使其和最大。
似乎是有如下结论，满足以上条件的一组数，总是存在一种顺序，使得按照题目要求的
取法总是可以取到全部的数；这个似乎是正确的，没仔细想
至于怎么找最大和，似乎可以用dp来做？
dp[i, j, k] 这是从i开始到j结束（闭区间）的（循环）子串里取k个的元素满足以上
条件的最大值；
dp[i, j, k] = max(dp[i+2, j-1, k - 1], input[j], dp[i, j, k])
^^^ 取i ^^^ 不取i
谁给验证一下 |
c********t
发帖数: 5706 | 33 给个反例吧。
★ 发自iPhone App: ChineseWeb 7.8
【在 y***g 的大作中提到】
: 不相邻也不一定能取道
:
: 明白了。 那就找到不相邻的 (N 2)/3 个元素,使sum最大。需要证明只要不相邻，一定
: 都能取到。
|
f*********d
发帖数: 140 | 34 V5!
"则在这M + 1块比萨间将会有M + 2个槽（考虑到比萨时环形的），我们将剩余的2M块
比萨放到这M + 2个槽里，"
M + 1 个slot吧(环形)，当然了，那会更有利于你的证明，不影响结论！
-
3
【在 p******9 的大作中提到】
: 这题可以转化成 在N个数的环形数组中取不相邻的N/3(上取整)，使这些数和最大。我
: 们可以证明任意这N/3个不相邻的数，必然能对应一种符合原题的取法。
: 可以用数学归纳法证明这个问题，为了方便，重新定义一下变量名，另M为我会取得到
: 的比萨数，则N有三种情况，即N=3M - 2 , N = 3M - 1, N = 3M，我们只证明N = 3M -
: 2这种情况，因为这个时候若能取到，N= 3M - 1或N = 3M 的时候肯定能取到。
: （1）基础条件：若M <= 3，我们可以枚举证明以上命题成立。
: （2）假设M的时候成立，我们证明M + 1的时候也成立。在M + 1的时候，将会有N = 3
: (M + 1) - 2= 3M + 1块比萨。而此时M + 1块比萨之间互不相邻，则在这M + 1块比萨
: 间将会有M + 2个槽（考虑到比萨时环形的），我们将剩余的2M块比萨放到这M + 2个槽
: 里，因为M >=3，基于鸽笼原理，必定会有两个比萨落到这个槽里。此时整个序列的形
|
