【HDOJ5951】Winning an Auction（博弈DP）

题意：A和B两个人做一个拍卖游戏。每一轮两人分别给出一个价格，出价高者获得该轮的物品，出价相同则奇数轮A优先，偶数轮B优先。

两个人的目标都是最大化自己的商品数量，给定轮数n与两人分别的总资金a,b，问都按最优策略行动下两人分别能获得多少物品

n,a,b<=255

思路：From https://www.cnblogs.com/jihe/p/6022569.html

dp[n][a][b]表示现在还有1-n标号的n件物品，a元钱的占据优势，
这样假设出价是u,该物品第一个人买就由上一个状态dp[n-1][b][a-u]了，这样就可以减去n的奇偶带来的状态
这道题有人0ms救过了，显然是可以推出公式的，不过暂时还没找到

神仙博弈……要找到平衡点

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<iostream>
 4 #include<algorithm>
 5 #include<cmath>
 6 typedef long long ll;
 7 using namespace std;
 8 #define N   256
 9 #define oo  10000000
10 #define MOD 1000000007
11         
12 int dp[N][N][N];
13 
14 int calc(int n,int a)
15 {
16     int t=n/2;
17     return t*a+(n-t)*(a+1);
18 }
19 
20 int main()
21 { 
22     for(int i=0;i<N;i++)
23      for(int j=0;j<N;j++)
24      {
25          if(i>=j) dp[1][i][j]=1;
26           else dp[1][i][j]=0;
27      }
28     for(int i=2;i<N;i++)
29      for(int a=0;a<N;a++)
30      {
31          int t=min(calc(i,a),N);     //剃光头
32         for(int b=0;b<t;b++)
33         {
34             if(a==b){dp[i][a][b]=(i+1)/2; continue;}  
35             int ta=i-dp[i-1][b][a]; //初始假设a买 
36             int tb=0;
37             int j=1;
38             while(1)
39             {
40                 if(b<j||(tb=(i-1-dp[i-1][b-j][a]))>=ta) //b继续抬价无意义 
41                 {
42                     dp[i][a][b]=ta;
43                     break;
44                 }
45                 if(a<j||(ta=(i-dp[i-1][b][a-j]))<=tb)  //a继续抬价无意义
46                 {
47                     dp[i][a][b]=tb;
48                     break;
49                 }
50                 j++; 
51             }
52         }
53     }
54              
55     int cas;
56     scanf("%d",&cas);
57     while(cas--)
58     {
59         int n,a,b;
60         scanf("%d%d%d",&n,&a,&b);
61         printf("Alice %d Bob %d
",dp[n][a][b],n-dp[n][a][b]);
62     }
63     return 0;
64 }
65