来个三俗的 - 未名空间MITBBS历史存档

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

Redian新闻

>未名空间

>Joke - 肚皮舞运动

来个三俗的

来个三俗的# Joke - 肚皮舞运动

r*82010-08-12 07:08

1 楼

两海盗在分金币，金币放在N个瓶子里，　每个瓶子放有金币，瓶子放在一排，两海盗
都知道每个瓶子放的金币数目，分的规则是这样的，每个海盗呢只也取边上的一个瓶子
，第一个，或最后一个。
请你写一算法，帮其中一海盗获得最可以多的金币，前提是两海盗可是一样的聪明啊。
给出算法复杂度，能用O（N*N）写出吗？

x*o2010-08-12 07:08

2 楼

x*p2010-08-12 07:08

3 楼

Using recursive.
Suppose an array A of integers is given to hold all golden pieces. Its index
is from 0 to N-1.
Let function f(int startIndex, int endIndex) returns the maximum money you
can get.
int f(A, int startIndex, int endIndex) {
int sum = summation from A[startIndex] to A[endIndex];
if (startIndex==endIndex) return A[startIndex];
int choice1 = sum - f(A, startIndex+1, endIndex);
int choice2 = sum - f(A, startIndex, endIndex-1);
return (choice1>choice2?choice1:choice2)
}
run f(A, 0, N-1)

r*u2010-08-12 07:08

4 楼

DP, 最近讨论过,考古一下.

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

: 两海盗在分金币，金币放在N个瓶子里，　每个瓶子放有金币，瓶子放在一排，两海盗
: 都知道每个瓶子放的金币数目，分的规则是这样的，每个海盗呢只也取边上的一个瓶子
: ，第一个，或最后一个。
: 请你写一算法，帮其中一海盗获得最可以多的金币，前提是两海盗可是一样的聪明啊。
: 给出算法复杂度，能用O（N*N）写出吗？