y****n
发帖数: 60 | 1 有50个硬币在一条线上。两个人轮流拿，只能拿两端的（比如说第一个人开始只能拿第
一或者第50个硬币）。什么算法可以让第一个人拿到的钱最多？ | C***m
发帖数: 120 | 2 First pick: add up coin 1,3,5,...,49, sum is A. Sum of coin 2,4,6,...,50 is
B. If A>B choose 1; if A
Every time, follow the similar strategy. Easy to see, player 1 could earn at
least Max(A,B). Feel it is the best, not a rigorous proof though. | C***m
发帖数: 120 | 3 这个方法不对，比如4个coin(5,1,5,6)。
可能还是得用DP来做,求大牛指点。
is
at
【在 C***m 的大作中提到】
: First pick: add up coin 1,3,5,...,49, sum is A. Sum of coin 2,4,6,...,50 is
: B. If A>B choose 1; if A: Every time, follow the similar strategy. Easy to see, player 1 could earn at
: least Max(A,B). Feel it is the best, not a rigorous proof though.
| A**u
发帖数: 2458 | 4 V(i,j) 是 考虑i,i+1,...,j-1,j个硬币是， max-gain
有. V(i,i) = C[i], 只剩下1个硬币.
当 j>i时,
V[i,j], 可以从左拿, 值是 C[i] - V(i+1,j)
从右拿，值是C[j] - V(i,j-1)
V(i,j) = max(C[i] - V(i+1,j), C[j] - V(i,j-1))
像Caxim说的，DP,或者递归 | C***m
发帖数: 120 | 5 挺好的，这里可能是要 V(i,j) = max(Sum_i^j C[k] - V(i+1,j), Sum_i^j C[k] - V(
i,j-1))
【在 A**u 的大作中提到】
: V(i,j) 是 考虑i,i+1,...,j-1,j个硬币是， max-gain
: 有. V(i,i) = C[i], 只剩下1个硬币.
: 当 j>i时,
: V[i,j], 可以从左拿, 值是 C[i] - V(i+1,j)
: 从右拿，值是C[j] - V(i,j-1)
: V(i,j) = max(C[i] - V(i+1,j), C[j] - V(i,j-1))
: 像Caxim说的，DP,或者递归
|
|
