h*******u
发帖数: 44 | 1 Given a pizza with 3n slices (e.g. 9, 12,...), repeatedly pick a slice (save
the size of this slice). When you do this, the slice on the left goes to
someone on the left, and the slice on the right goes to someone on the right
. Repeat this process until no slices are left. How can you write a program
to find a list of slices that has the maximum sum?
As an example, assume the pizza has been sliced as follow: 1, 2, 10, 3, 11,
4. You may select the third slice of pizza(i.e. 10). The second and fourth
slice will disappear, leaving a pizza with 1, 11, 4. You could then select
one of the slices, such as the second slice (i.e. 11) and the other two
would disappear. This would eat a total of 21, the maximum possible for this
example.
Detail explanation of above example:
your list is 1 2 10 3 11 4.
1) pick 10
2) 2,3 will be eliminated
3) your current list is: 1 11 4
4)pick 11
5) 1,4 will be eliminated
6) Done
So the sum is: 10+11=21 | w*********4
发帖数: 832 | | l****u
发帖数: 1764 | 3 貌似不是greedy，也没太好的办法dp，除了brute force，真没想到什么好的dp方法呢
，sub problem貌似非常多啊。。 | l****u
发帖数: 1764 | 4 想到一个用dp的方法，如果slices数量比较小（小于30），可以用一个整形数组表示
sub problem，比如dp[111111111]表示完整pizza（9个slices）的最优解，dp[
111110001]表示第2个slice被拿掉的最优解，dp[100010001]表示第2个slice和第6个
slice被拿掉的最优解
数组下标是二进制表示，最多可以表示30个slice的问题
如果要超过30个（一个pizza切30块也差不多了吧？），那可能就得用string做下标，
存在hashmap里面了
base case 是只剩3个slice的时候(可以用位操作判断这个条件)，dp[0.a.b.c.0] =
max(dp[0.a.0],dp[0.b.0],dp[0.c.0]) | h*h
发帖数: 23 | 5 这个跟Leetcode这道题是一样的：
https://leetcode.com/problems/house-robber-ii/
用DP可以解
save
right
program
,
this
【在 h*******u 的大作中提到】
: Given a pizza with 3n slices (e.g. 9, 12,...), repeatedly pick a slice (save
: the size of this slice). When you do this, the slice on the left goes to
: someone on the left, and the slice on the right goes to someone on the right
: . Repeat this process until no slices are left. How can you write a program
: to find a list of slices that has the maximum sum?
: As an example, assume the pizza has been sliced as follow: 1, 2, 10, 3, 11,
: 4. You may select the third slice of pizza(i.e. 10). The second and fourth
: slice will disappear, leaving a pizza with 1, 11, 4. You could then select
: one of the slices, such as the second slice (i.e. 11) and the other two
: would disappear. This would eat a total of 21, the maximum possible for this
| h*******u
发帖数: 44 | 6 不是很一样，因为house是一直在哪里，而pizza选择完之后是要把周围扔掉的，这样数
组的下标会发生变化。
【在 h*h 的大作中提到】
: 这个跟Leetcode这道题是一样的：
: https://leetcode.com/problems/house-robber-ii/
: 用DP可以解
:
: save
: right
: program
: ,
: this
| N******G
发帖数: 33 | 7 f(i,j)代表：如果只有i...j这些pizza，最优的结果
要求f(1,n)
f(i,i+2)=pizza[i+1]
假定最后留下三块pizza, i<=a1
选的，a2,a3同理
所以可以枚举a1,a2,a3,递归处理：
f(i,j)=max_{i<=a1
pizza[a2]
因为a2定了以后，a1和a3独立，所以复杂度是O(n^4)
可以再想想如何优化到n^3 | i********x
发帖数: 2 | 8 https://www.quora.com/Given-a-pizza-with-3n-slices-e-g-9-12-repeatedly-pick-
a-slice-save-the-size-of-this-slice-When-you-do-this-the-slice-on-the-left-
goes-to-someone-on-the-left-and-the-slice-on-the-right-goes-to-someone-on-
the-right-Repeat-this-process-until-no-slices-are-left-How-can-you-write-a-
program-to-find-a-list |
|
