首页 > 代码库 > hdu 5951

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\n",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救过了,显然是可以推出公式的,不过暂时还没找到
*/

hdu 5951