刚一卸任就杯具了 - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>PhotoGear - 摄影器材

刚一卸任就杯具了

刚一卸任就杯具了# PhotoGear - 摄影器材

t*h2010-08-26 07:08

1 楼

前段时间有个朋友在班上提到的pizza问题
有一块pizza，被分成n个slices。有两个人来分这块pizza。规则是你先拿一块，你的
对手拿你之前拿掉的相连的两块。设计算法，拿到最多的pizza。
这个朋友提到面试官说有O(n2)的算法，我想了半天也没有一丁点主意。
看上去至少是O(n3)。
请教大家怎么解决这个分pizza的问题。
★ 发自iPhone App: ChineseWeb 7.8

n*s2010-08-26 07:08

2 楼

诚征版主中 [您的信箱超过容量,不能再收信!] 讨论区 [
Tianjin]

a*32010-08-26 07:08

3 楼

环形dp，最常用的方法，把输入double一下，变成线性dp。
如输入{1,5,7,8,6,4,2}double下，变成{1,5,7,8,6,4,2,1,5,7,8,6,4,2}
在新的序列上做线性dp
dp[i][k]定义为，以i开始，长度为k的环形序列最终能得到的最大值。
那么dp[i][k] = max{dp[i][k-3]+array[i+k-2],dp[i+1][k-3]+array[i+k-1],dp[i+2]
[k-3]+array[i],...,dp[i+k-1][k-3]+array[i+k-3]}
length = 初始序列长度
最终看max{dp[i][length]}的结果（貌似应该是一样的才对？）
这个是O(n^3)的，O(n^2)，貌似需要特殊优化，没想出来。

a*a2010-08-26 07:08

4 楼

终于不怕你威胁了

【在 n*****s 的大作中提到】

: 诚征版主中 [您的信箱超过容量,不能再收信!] 讨论区 [
: Tianjin]

w*y2010-08-26 07:08

5 楼

我看到这个答案
http://www.mashengjun.info/?p=1045
但是这个题目怎么回事／怎么分析我还完全摸不着头脑 [email protected]#$%⋯⋯&

n*s2010-08-26 07:08

6 楼

也不怕你blackmail了

【在 a***a 的大作中提到】

: 终于不怕你威胁了

d*x2010-08-26 07:08

7 楼

我靠，看了最新回复我发现所有的人都理解错题意了！！
很可能包括楼主在内！！
原来对手不是拿掉相邻的两块，而是从相邻的两块里面拿！！
坑爹呢！！

【在 t*****h 的大作中提到】

: 前段时间有个朋友在班上提到的pizza问题
: 有一块pizza，被分成n个slices。有两个人来分这块pizza。规则是你先拿一块，你的
: 对手拿你之前拿掉的相连的两块。设计算法，拿到最多的pizza。
: 这个朋友提到面试官说有O(n2)的算法，我想了半天也没有一丁点主意。
: 看上去至少是O(n3)。
: 请教大家怎么解决这个分pizza的问题。
: ★ 发自iPhone App: ChineseWeb 7.8

a*a2010-08-26 07:08

8 楼

我现在就封泥

【在 n*****s 的大作中提到】

: 也不怕你blackmail了

l*82010-08-26 07:08

9 楼

不同的两个问题

【在 d**********x 的大作中提到】

: 我靠，看了最新回复我发现所有的人都理解错题意了！！
: 很可能包括楼主在内！！
: 原来对手不是拿掉相邻的两块，而是从相邻的两块里面拿！！
: 坑爹呢！！

n*s2010-08-26 07:08

10 楼

睡觉睡觉

【在 a***a 的大作中提到】

: 我现在就封泥

w*y2010-08-26 07:08

11 楼

en 应该是从豁口相邻两块拿
这是英文版的讨论， http://programmers.stackexchange.com/questions/124417/how-is-the-pizza-picking-problem-solved-using-dynamic-programming-techniques
我更看不懂@@

【在 d**********x 的大作中提到】

G*A2010-08-26 07:08

12 楼

一个笨办法：第一块的选择有n种.一旦第一块选定了，后面就是线性dp。
不过复杂度自然 O(n^3)

【在 t*****h 的大作中提到】

w*y2010-08-26 07:08

13 楼

我感觉2楼的回答应该是针对拿走相邻的两块，因为有-2 -3什么的，不过我还是完全不
懂hehe

【在 l*********8 的大作中提到】

: 不同的两个问题

t*h2010-08-26 07:08

14 楼

哈哈 lz的表述比较坑跌

【在 d**********x 的大作中提到】

f*t2010-08-26 07:08

15 楼

拿走第一块后为什么就是线性DP了？

【在 G****A 的大作中提到】

: 一个笨办法：第一块的选择有n种.一旦第一块选定了，后面就是线性dp。
: 不过复杂度自然 O(n^3)

f*s2010-08-26 07:08

16 楼

写了一个，欢迎找错：
int maxpissa(vector arr){
int n=arr.size();
if(n==0) return 0;
if(n==1) return arr[0];
if(n==2) return max(arr[0], arr[1]);
int total[n][n]=all 0;
int dp[n][n]=all 0;
for(int i=0;itotal[i][i]=arr[i];
dp[i][i]=arr[i];
}

for(int i=0;ifor(int j=i+1;jtotal[i][j]=total[i][j-1]+arr[j];

for(int i=0;idp[i][i+1]=max(arr[i], arr[i+1]);

for(int L=3;L<=n;L++){
for(int i=0;iint j=i+L-1;
dp[i][j]=total[i][j]-min(dp[i][j-1], dp[i+1][j]);
}
}
return dp[0][n-1];
}