f**********w
发帖数: 93 | 1 两个人（A，B）参与一个游戏，规则如下：
1）一个随机的整数数列有偶数个数,a1,a2,...a2n
2）A先从数列取数，但只能从两头取,a1 or a2n
3)然后Ｂ取数，也是只能从剩下的两头取，依此类推，两个人轮流，都只能从两头取
４）最后谁手里的数和最大赢。
那位能给个好的思路，谢谢 | l****i
发帖数: 396 | | x****k
发帖数: 2932 | 3 这题版上讨论过，用dp做，具体答案不记得了，我重新做了一下，有错请指出。
设 F(i,j)为先取者从ai ~ aj取出来的最大sum，则
F(i,j) = max(ai + min(F(i+2,j), F(i+1,j-1)), aj + min(F(i,j-2), F(i+1,j-1))) | x****k
发帖数: 2932 | 4 当然，截止条件是
F(i, j)= max(ai, aj) when i + 1 = j， 对于先取者A | j****a
发帖数: 55 | 5 楼上的看起来比较elegant，我随笔写的，不知道对错啊...
// assume A picks first, return difference between what A picks and what B
picks.
int pickNumber(int* array, int begin, int end, HashTable* hashTable) {
int result;
if (getFromHash(hashTable, begin, end, &result)) {
return result;
}
if (end == begin) {
putToHash(hashTable, begin, end, -array[begin]);
return -array[begin];
}
int diff1 = pickNumber(array, begin + 1, end);
int diff2 = pickNumber(array, begin, end + 1);
if ((end - begin) % 2) { // A is picking
if (diff1 + array[begin] > diff2 + array[end]) {
return diff1 + array[begin];
} else {
return diff2 + array[end];
}
} else {
if (diff1 + array[begin] > diff2 + array[end]) {
return diff2 + array[end];
} else {
return diff1 + array[begin];
}
}
} | c*******t
发帖数: 1095 | | h*******d
发帖数: 69 | 7 could you explain why use min?
))
【在 x****k 的大作中提到】
: 这题版上讨论过，用dp做，具体答案不记得了，我重新做了一下，有错请指出。
: 设 F(i,j)为先取者从ai ~ aj取出来的最大sum，则
: F(i,j) = max(ai + min(F(i+2,j), F(i+1,j-1)), aj + min(F(i,j-2), F(i+1,j-1)))
| d**e
发帖数: 6098 | 8 因为对手也采取同样的策略，所以他会令你取得最少，然后到你时你要用这个最少加上
当前能取最大的值。
此题在本版第一次出现是在这里。
http://mitbbs.com/article_t/JobHunting/31678287.html
【在 h*******d 的大作中提到】
: could you explain why use min?
:
: ))
| s*******r
发帖数: 47 | 9 min() 表示的是assume另一个人也用最佳策略?
【在 h*******d 的大作中提到】
: could you explain why use min?
:
: ))
| h*******d
发帖数: 69 | 10 thanks!
【在 d**e 的大作中提到】
: 因为对手也采取同样的策略，所以他会令你取得最少，然后到你时你要用这个最少加上
: 当前能取最大的值。
: 此题在本版第一次出现是在这里。
: http://mitbbs.com/article_t/JobHunting/31678287.html
|
|
