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

fudq's AC Road

何以解忧,唯有AC!

 
 
 

日志

 
 

hdu 1514 Free Candies  

2014-03-03 21:23:05|  分类: ACM-hdu |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
题意:
有4堆糖果,每堆糖果有n个,从上到下排好,取糖果只能从上往下取,取完的糖果放在篮子里,篮子里最多放5个,如果篮子里有两个颜色相同的糖果则可以取走放进口袋里,问最多能取走多少对糖果放进口袋。n<=40, 糖果颜色最多20种。
题解:
记忆化搜索,搜索过程中利用set模拟。

//hdu 1514
int n,ans,h[5],f[42][5],dp[42][42][42][42];

set<int> S;
set<int>::iterator it;

int deal(int a)
{
it=S.find(a);
if(it!=S.end())
{
S.erase(a);
return 1;
}
S.insert(a);
return 0;
}

int dfs(int tmp)
{
if(dp[h[0]][h[1]][h[2]][h[3]] != -1)
return dp[h[0]][h[1]][h[2]][h[3]];
int tt=0;
for(int i=0;i<4;i++)
{
if(h[i] < n && S.size() < 5)
{
int t=deal(f[h[i]][i]);
if(S.size() < 5)
{
h[i]++;
tt=max(tt,dfs(tmp+t));
h[i]--;
}
tt=max(tt,tmp+t);
if(t == 1)
S.insert(f[h[i]][i]);
else
S.erase(f[h[i]][i]);
}
}
return dp[h[0]][h[1]][h[2]][h[3]]=tt;
}

int main()
{
#ifndef ONLINE_JUDGE
freopen("testin.txt","r",stdin);
//freopen("testout.txt","w",stdout);
#endif
while(sf(n) && n)
{
fr(n){
for(int j=0;j<4;j++)
sf(f[i][j]);
}
ans=0;h[0]=h[1]=h[2]=h[3]=0;
memset(dp,-1,sizeof(dp));
pf(dfs(0));
}
return 0;
}



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

历史上的今天

在LOFTER的更多文章

评论

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

页脚

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