hdu 5951（博弈）

#include<bits/stdc++.h>
using namespace std;
const int maxn=256;
int sg[maxn][maxn][maxn]={0};

inline int geta(int n,int a){
    int t=n/2;
    return t*a+(n-t)*(a+1);
}

int main(){

    for(int a=0;a<maxn;a++)
        for(int b=0;b<maxn;b++)
            if(a>=b)sg[1][a][b]=1;
            else sg[1][a][b]=0;

    for(int i=2;i<maxn;i++){
        for(int a=0;a<maxn;a++){
            int tt=geta(i,a);tt=min(maxn,tt);
            for(int b=0;b<tt;b++){

                if(a==b){sg[i][a][b]=(i+1)/2;continue;}

                int va = i-sg[i-1][b][a];//初始a买的状态
                int vb=0;
                for (int u = 1; ; ++u){
                    if (b <u || (vb = (i-1-sg[i-1][b-u][a])) >= va)    //b多花钱没意义
                    {
                        sg[i][a][b] = va;
                        break;
                    }
                    if (a < u||(va=(i-sg[i-1][b][a-u] )) <= vb)     //a多花钱没意义
                    {
                        sg[i][a][b]=vb;
                        break;
                    }
                }
            }
        }
    }

    int t,n,a,b;
    scanf("%d",&t);
    while(t--){
        scanf("%d%d%d",&n,&a,&b);
        int aa=sg[n][a][b],bb=n-aa;
        printf("Alice %d Bob %d
",aa,bb);
    }
    return 0;
}

 /*n件物品，两个人分别有a,b元钱，对这n件物品进行出价，然后第一个人在第奇数个物品的时候优势，偶数相反，
优势即两个人出价相同，有优势的人获得
开始想打表，结果状态数太大，需要大约4s才能打完表，1.6e7个状态无法交表，
然后请教了hdu_snowy_smile,加入了如果当前出价两个人结果会更差或者无力出价
就停止继续出价，这样就可以在300ms打出表，剩下的离线回答就好了
dp[n][a][b]表示现在还有1-n标号的n件物品，a元钱的占据优势，
这样假设出价是u,该物品第一个人买就由上一个状态dp[n-1][b][a-u]了，这样就可以减去n的奇偶带来的状态
这道题有人0ms救过了，显然是可以推出公式的，不过暂时还没找到
*/