v******a
发帖数: 54 | 1 Consider the following game. A "dealer" produces a sequence s1 … sn of "
cards," face up, where
each card si has a value vi . Then two players take turns picking a card
from the sequence, but can only pick the first or the last card of the
(remaining) sequence. The goal is to collect cards of largest total value.
(For example, you can think of the cards as bills of different denominations
.)
Assume n is even.
Give an O(n*n) algorithm to compute an optimal strategy for the first player
. Given th | h**6
发帖数: 4160 | 2 生成一个n*n的矩阵，里面全是0和1，表示剩余部分的开始结束位置分别为i和j时从前
面还是后面取。 | A*********r
发帖数: 564 | 3 令Ｆ（ｉ，ｊ）表示从范围ｉ．．ｊ中取头或尾能得到的最大ｖａｌｕｅ，
那么
F(i,j)=max { min {F(i+1,j-1), F(i+2,j)}+Vi, min {F(i+1,j-1), F(i,j-2))}+Vj }
第一项是取了ｉ的话，至少能够得到的值（对手可能取剩下的ｉ＋１或者ｊ），第二项
是取了ｊ的话，至少能够得到的值。。
下面这个ｌｉｎｋ的第１０道题，基本上一样吧。。
http://people.csail.mit.edu/bdean/6.046/dp/
denominations
player
【在 v******a 的大作中提到】
: Consider the following game. A "dealer" produces a sequence s1 … sn of "
: cards," face up, where
: each card si has a value vi . Then two players take turns picking a card
: from the sequence, but can only pick the first or the last card of the
: (remaining) sequence. The goal is to collect cards of largest total value.
: (For example, you can think of the cards as bills of different denominations
: .)
: Assume n is even.
: Give an O(n*n) algorithm to compute an optimal strategy for the first player
: . Given th
| p********7
发帖数: 549 | 4 正解
}
【在 A*********r 的大作中提到】
: 令Ｆ（ｉ，ｊ）表示从范围ｉ．．ｊ中取头或尾能得到的最大ｖａｌｕｅ，
: 那么
: F(i,j)=max { min {F(i+1,j-1), F(i+2,j)}+Vi, min {F(i+1,j-1), F(i,j-2))}+Vj }
: 第一项是取了ｉ的话，至少能够得到的值（对手可能取剩下的ｉ＋１或者ｊ），第二项
: 是取了ｊ的话，至少能够得到的值。。
: 下面这个ｌｉｎｋ的第１０道题，基本上一样吧。。
: http://people.csail.mit.edu/bdean/6.046/dp/
:
: denominations
: player
| m**q
发帖数: 189 | 5 这样行不行？
因为目的是想让自己多得分，对方少得分，既然每人取n/2个，
相当于想办法使得自己得分比对方得分多得越多越好。
设f(i,j)表示范围i...j中所得获得的最大分差(自己总分 - 对方总分）
f(i,j) = max { f(i+1,j-1) + Vi - Vj,
f(i+2,j) + Vi - Vi+1,
f(i+1,j-1) + Vj - Vi,
f(i,j-2) + Vj - Vj-1 }
我觉得这个的最优解应该和你的是一样的。
2))}+Vj }
【在 A*********r 的大作中提到】
: 令Ｆ（ｉ，ｊ）表示从范围ｉ．．ｊ中取头或尾能得到的最大ｖａｌｕｅ，
: 那么
: F(i,j)=max { min {F(i+1,j-1), F(i+2,j)}+Vi, min {F(i+1,j-1), F(i,j-2))}+Vj }
: 第一项是取了ｉ的话，至少能够得到的值（对手可能取剩下的ｉ＋１或者ｊ），第二项
: 是取了ｊ的话，至少能够得到的值。。
: 下面这个ｌｉｎｋ的第１０道题，基本上一样吧。。
: http://people.csail.mit.edu/bdean/6.046/dp/
:
: denominations
: player
|
|
