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

OI之路,漫漫人生

只为梦想,没有理由

 
 
 

日志

 
 

POJ1946Cow Cycling题解  

2014-03-09 19:20:16|  分类: POJ |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
                                                                      奶牛蹬车队
                                                       BY   LGS
题目大意:一共有N个奶牛在团体赛跑,共跑D圈,每个奶牛的初始值相同都为E。奶牛队分为头领和其余队员,队伍每分钟若跑X圈头领需要消耗X^2的体力,其余队员只需消耗X的体力。每个整数分钟可以换头领。求跑到D圈的最终耗时。

题解:此题一年半前做过,当时感觉太难了,写搜索拿了40分吧。现在来做,发现挺水的。自己想了想题目,首先要明白这点:1.一开始每个奶牛的初始体力值都相同,假定先把第一个作为头领(无所谓的)。那么如果你骑到半路里换了奶牛了,等会一定不需要再换回来,也就是说每个奶牛最多只当头领1次。2。贪心是错误的,直接把每个牛奶做头领然后全部消耗完,虽然样例过了,很明显如果跑的圈数少,直接可以换奶牛的。于是题目便简化了许多:首先,我们可以一头一头枚举奶牛当头领了,其次,对于当前的奶牛,有两种扩展的状态,要么继续当头领,要么换头领。最后,我们只需要记录当前奶牛的体力值,不需要记录后面的奶牛,因为后面的奶牛还没当头领,他们的体力值一定是E-已走路程J。这样我们便很容易选择DP,写好方程,一共需要记录的状态有3个,当前的奶牛i,已走路程j,当前奶牛头领的体力值p。

总结:太开心了,一遍就写了个AC的DP,爽!
核心代码: for (i=1;i<=n;i++)
  for (j=0;j<=d-1;j++)
   for (p=e;p>=0;p--)
   if (f[i][j][p]!=maxn)
    for (k=1;k<=p;k++)
                {
    if (p>=k*k) 
    {f[i][j+k][p-k*k]=min(f[i][j+k][p-k*k],f[i][j][p]+1);
     if (j+k>=d) ans=min(ans,f[i][j+k][p-k*k]);
    }
    if (i+1<=n&&(e-j>=k*k))
    {f[i+1][j+k][e-j-k*k]=min(f[i+1][j+k][e-j-k*k],f[i][j][p]+1);
     if (j+k>=d) ans=min(ans,f[i+1][j+k][e-j-k*k]); 
    }
                }
  评论这张
 
阅读(13)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

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

页脚

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