题目链接: http://vjudge.net/problem/viewProblem.action?id=25636
对于>1的堆,必然会被其中一人全部合并。
然后就是二维dp,dp[非1堆的操作数][1堆个数]。
#include <stdio.h>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <cmath> using namespace std;
#define lson o<<1
#define rson o<<1|1
#define max(a,b) (a)>(b)?(a):(b)
#define min(a,b) (a)<(b)?(a):(b)
#define INF 200000000 typedef long long ll;
int dp[][];
int dfs(int one,int tot){
if(dp[one][tot]>-)return dp[one][tot];
if(tot==)return dp[one][tot]=dfs(one+,);
if(one==)return dp[one][tot]=tot&;
if(tot>&&!dfs(one,tot-))return dp[one][tot]=;
if(!dfs(one-,tot))return dp[one][tot]=;
if(tot&&!dfs(one-,tot+))return dp[one][tot]=;
if(one>=)
if((tot&&!dfs(one-,tot+))||(!tot&&!dfs(one-,tot+)))
return dp[one][tot]=; return dp[one][tot]=;
}
int main(){
int t,cs,n;
scanf("%d",&t);
memset(dp,-,sizeof dp);
dp[][]=;
for(cs=;cs<=t;cs++){
scanf("%d",&n);
int x,one=,tot=;
for(int i=;i<n;i++){
scanf("%d",&x);
if(x==)one++;
else
tot+=x+;
}
if(tot)tot--;
printf("Case #%d: ",cs);
if(dfs(one,tot))printf("Alice\n");
else printf("Bob\n");
}
return ;
}