注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

fudq's AC Road

何以解忧,唯有AC!

 
 
 

日志

 
 

hdu 4597 Play Game  

2013-12-16 17:05:33|  分类: ACM-hdu |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
http://acm.hdu.edu.cn/showproblem.php?pid=4597
题意:2013年通化邀请赛题目。有两堆牌,每张牌上有一个分值,每次取只能取其中一堆的头部或者尾部的牌,两个人轮流抽牌,采用最优策略,问先手最多能得到多少分。
题解:记忆化搜索。as和ae表示一堆的头和尾,bs和be表示另一堆的头和尾,f[as][ae][bs][be]表示当前状态下所能得到的最多分数。则f[as][ae][bs][be]等于当前所有分数和 - 下一状态的最多分数,按每种状态记忆化搜索下即可。

int a[22],b[22],sa[22],sb[22];
int f[22][22][22][22];


int dfs(int as,int ae,int bs,int be)
{
if(as > ae && bs > be)
return f[as][ae][bs][be]=0;
if(f[as][ae][bs][be] != -1)
return f[as][ae][bs][be];

int s=0,tmp=0;
if(as <= ae)
s+=sa[ae]-sa[as-1];
if(bs <= be)
s+=sb[be]-sb[bs-1];

if(as <= ae) //四种状态转移
{
tmp=max(tmp,s-dfs(as+1,ae,bs,be));
tmp=max(tmp,s-dfs(as,ae-1,bs,be));
}
if(bs <= be)
{
tmp=max(tmp,s-dfs(as,ae,bs+1,be));
tmp=max(tmp,s-dfs(as,ae,bs,be-1));
}
return f[as][ae][bs][be]=tmp;
}

int main()
{
#ifndef ONLINE_JUDGE
freopen("testin.txt", "r", stdin);
// freopen("textout.txt", "w", stdout);
#endif
int T,n;
sf(T);
while(T--)
{
sf(n);sa[0]=0;sb[0]=0;
for(int i=1;i<=n;i++)
{
sf(a[i]);
sa[i]=sa[i-1]+a[i];
}
for(int i=1;i<=n;i++)
{
sf(b[i]);
sb[i]=sb[i-1]+b[i];
}
memset(f,-1,sizeof(f));
dfs(1,n,1,n);
printf("%d\n",f[1][n][1][n]);
}
return 0;
}



  评论这张
 
阅读(72)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017