H*M
发帖数: 1268 | 1 没小尾羊同学的那么复杂，呵呵。
你和你对手玩游戏。 有一溜银币，偶数，每块有个面值(已知，V1,V2,..Vn)。你和对手
轮流拿，可以从头拿或者从尾拿。
现在要你求出如果你第一个拿的话，最大可能的保守的钱数。也就是说，不管对手怎么
拿，the maximum possile of money You definitely (garantee)can get. | g*******y
发帖数: 1930 | 2 DP肯定能做的，不过先问问，有比O(N^2)更好的解吗
对手
【在 H*M 的大作中提到】
: 没小尾羊同学的那么复杂，呵呵。
: 你和你对手玩游戏。 有一溜银币，偶数，每块有个面值(已知，V1,V2,..Vn)。你和对手
: 轮流拿，可以从头拿或者从尾拿。
: 现在要你求出如果你第一个拿的话，最大可能的保守的钱数。也就是说，不管对手怎么
: 拿，the maximum possile of money You definitely (garantee)can get.
| t********e
发帖数: 25 | 3 DP.
Hint: The iteration func is of Sij = max_min form | S*********a
发帖数: 1640 | 4 如果题意是要求不败策略的话。
把奇数和偶数上Vi分别加起来。如果奇数大就永远只拿奇数位上硬币，反之永远拿偶数
位上的。
因为你先拿，你能保证每次都能拿走奇/偶位的硬币，留下头和尾都是偶/奇位的给对手。
O(n)
对手
【在 H*M 的大作中提到】
: 没小尾羊同学的那么复杂，呵呵。
: 你和你对手玩游戏。 有一溜银币，偶数，每块有个面值(已知，V1,V2,..Vn)。你和对手
: 轮流拿，可以从头拿或者从尾拿。
: 现在要你求出如果你第一个拿的话，最大可能的保守的钱数。也就是说，不管对手怎么
: 拿，the maximum possile of money You definitely (garantee)can get.
| r**u
发帖数: 1567 | 5 如果有5个coin，v1, v2, v3, v4, v5, sum(V_even) > sum(V_odd)，只能从头或尾拿
，你第一次怎么能拿到一个V_even?
手。
【在 S*********a 的大作中提到】
: 如果题意是要求不败策略的话。
: 把奇数和偶数上Vi分别加起来。如果奇数大就永远只拿奇数位上硬币，反之永远拿偶数
: 位上的。
: 因为你先拿，你能保证每次都能拿走奇/偶位的硬币，留下头和尾都是偶/奇位的给对手。
: O(n)
:
: 对手
| S*********a
发帖数: 1640 | 6 题目不是说了偶数个硬币嘛
【在 r**u 的大作中提到】
: 如果有5个coin，v1, v2, v3, v4, v5, sum(V_even) > sum(V_odd)，只能从头或尾拿
: ，你第一次怎么能拿到一个V_even?
:
: 手。
| r**u
发帖数: 1567 | 7 你是对的，我没仔细看题。。。
【在 S*********a 的大作中提到】
: 题目不是说了偶数个硬币嘛
|
|
