首页 > 代码库 > 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
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。