HDU 5951 Winning an Auction 博弈论DP


http://acm.hdu.edu.cn/showproblem.php?pid=5951

Winning an Auction

Problem Description

Alice and Bob play an auction game. Alice has A dollars and Bob has B dollars initially. There are N items on sale. In each round, an item will be sold by the following way. Alice writes down an integer a (0 ≤ a ≤ A) and Bob writes down an integer b (0 ≤ b ≤ B), which are the amount of dollars they want to pay for the item. If a > b, then Alice gets the item and pays a dollars to the seller. If a < b, then Bob gets the item and pays b dollars to the seller. If a = b, then for the 1st, 3rd, 5th, 7th ... round, Alice gets the item and pays a dollars; for the 2rd, 4th, 6th, 8th ... round, Bob gets the item and pays b dollars. Since all the items have the same value, the goal of the auction game is to get as many items as possible. Both Alice and Bob know the values of N,A and B. Your task is to calculate how many items they will get if both of them play optimally.

Input

The first line is the number of test cases.
Each test case contains 3 integers N,A and B, which are no larger than
255.

Output

For each test case, output the number of items
Alice and Bob will get if both of them play optimally.

Sample Input

3
1 1 2
2 4 2
3 3 3

Sample Output

Alice 0 Bob 1
Alice 1 Bob 1
Alice 2 Bob 1

Source

 
题意
两个人竞拍n个物品,A有a元钱,B有b元钱。出价高的人获得该物品,如果出价相同,奇数轮物品A获得,否则B获得,两人都以最优策略获得尽量多的物品进行竞拍,问最后这两个人各获得了多少物品。
思路
很容易想到一点,如果要放弃这个物品,那么竞拍的时候出价0元就好了。采用到倒推的方法,用dp[o][p][a][b]表示开始的时候是物品的奇偶性(o=1为奇数)为o,剩余p个物品,A有a元钱,B有b元钱,A最多能获得的物品的个数。当A占优势的时候(为奇数轮的时候),假设A出了u元,那么B想要获得这个物品,必须要出u+1的钱,但是如果出了之后,并没有让A的收益变少,就可以舍弃这个物品了(出价0元)。这时,如果B竞拍这个物品成功会使A的收益减少,A就会继续加价,如果加价之后并不会让A的收益变多,那么A就放弃……如此循环下去直到B的钱不够竞拍或者满足上述的要求。B占优势的时候也是类似的。最后预处理一下这个dp就可以了。

 

 

HDU5724 Chess SG函数

http://acm.hdu.edu.cn/showproblem.php?pid=5724

Chess

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 986    Accepted Submission(s): 425

Problem Description
Alice and Bob are playing a special chess game on an n × 20 chessboard. There are several chesses on the chessboard. They can move one chess in one turn. If there are no other chesses on the right adjacent block of the moved chess, move the chess to its right adjacent block. Otherwise, skip over these chesses and move to the right adjacent block of them. Two chesses can’t be placed at one block and no chess can be placed out of the chessboard. When someone can’t move any chess during his/her turn, he/she will lose the game. Alice always take the first turn. Both Alice and Bob will play the game with the best strategy. Alice wants to know if she can win the game.
Input
Multiple test cases.
The first line contains an integer T(T100) , indicates the number of test cases.
For each test case, the first line contains a single integer n(n1000) , the number of lines of chessboard.
Then n lines, the first integer of ith line is m(m20) , indicates the number of chesses on the ith line of the chessboard. Then m integers pj(1pj20) followed, the position of each chess.
Output
For each test case, output one line of “YES” if Alice can win the game, “NO” otherwise.
Sample Input
2
1
2 19 20
2
1 19
1 18
 Sample Output
NO
YES
 Author
HIT
 Source
题意:有一个n*20的棋盘,有些地方有棋子,两人分别操作棋子,每个棋子只能往右走,如果这个其中右边是空位,则往右走一步,否则跳过右边的棋子,直到找到第一个空位。但是,无论怎样,都不能走出棋盘。当某个人不能移动任何棋子的时候,对方获胜。问在最优策略下,先手是必胜还是必败。
思路:可以看做20个相互独立的子游戏,对于每一个子游戏来说,用一个二进制数的01的位置来表示棋子的位置,一个状态转移出的状态不超过20个,可以求其SG值,当然,(2^i)-1这些状态的SG值是肯定等于0的。从这些状态倒推,预处理出其他状态的SG值(PS:SG为该状态的所有子状态的SG值中,未出现过的最小非负数,如果SG为0,这个状态为必输的)。对于每一次询问,将读入的位置转化为状态,再将每个状态异或,如果非零就是必胜,否则为必败。