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

keky的博客

GAIN CONFIDENCE _=_!既然选择了远方,便只顾风雨兼程^_^

 
 
 

日志

 
 

hoj1215 && 2035  

2007-10-18 18:42:07|  分类: cs_acm |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

       今天做了这两题,AC题终于到200了,这两题也是困扰我时间最长的题了,首先说说2035吧,大概题意是给你一堆点问是否存在一个两边对称的中心点,上学期就开始做,一直没过,当时也没想到什么好方法,后面向xiaoE问了问,有了大概的思路但后面又发现当输入奇数个点的时候又不好处理了,又放了好长时间,今天上课没事也不知怎么的就想到它,咦。好像有了,首先对那些点按X-Y坐标从小到大排下续,然后分别从两边往里头找,如果每对点的中心点都一样,那就说明存在那样的中心点,否则就不存在。

     两边的指针用 ft, lt表示; while( ft <= lt ){ ft++, lt-- } 循环几次即可搞定。这样也可以解决奇数点的问题,当num %2 == 0, 最后一次处理是ft = lt - 1; 当 num % 2 != 0 ,最后一次处理是ft = lt; 回来改改CODE一交竟然过了,嘿嘿!

      1215是简单的0-1背包题,前天刚看了那算法的大概,所以对我来说其实也不简单啦!刚开始时题意的理解出现了重大的错误,还以为要找正好能够达到HP的FOOD,而且输出就是那些FOOD的SCORE的和,交了N回都是WA,天啊,真可怜!最后无赖之下还是厚着脸皮找了xiaoE,之后才知道自己的理解能力是那么的差,唉!题目意思是比赛里的人物首先必须先加满血,之后吃的FOOD才能给他增加score,之前吃的不加SCORE,用DP实现,大致如下:

for( i = 1; i <= num; i++ )
  {
         j = i % 2;
            int f = ( i + 1 ) % 2;   
   for( int k = 1; k <= hp; k++ )
   {
       if( k > ch[i][0] ) temp = map[f][k-ch[i][0]];
                else  temp = 0;
                map[j][k] = map[f][k] < ( temp + ch[i][1]) ? map[f][k] : ( temp + ch[i][1]);     
   }    
  }

ch[][0] => hp值, ch[][1] => score;

   其中先把map[][]均置为大于可能出现的最大数的数,且map[][0] = 0;    http://acm.hit.edu.cn/ojs/show.php?Proid=1215&Contestid=0 喜欢打游戏的可以看看,好玩!。。

  评论这张
 
阅读(248)| 评论(4)
推荐 转载

历史上的今天

评论

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

页脚

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