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

vfleaking的博客

My name is VFlea King

 
 
 

日志

 
 

1197: [HNOI2006]花仙子的魔法  

2013-03-11 21:39:58|  分类: 衡阳八中 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
【题目大意】
就是n个球最多能把空间划分成多少个部分。
【题解】
尝试下n = 3的情况想象下……再看下面的内容……

谜之声:笑?3维太水了!我空手就能想象11维空间,vfk你又在鄙视人……
你是学量子力学的?!
谜之声:对啊!
……我无话可说了……反正我是想象不出来。

对n维区域用m个求划分,答案记为f(n, m)
对于第m个球,那么最优情况是它与所有球相交对吧~
然后相交时球是n维的,球面是n-1维的,球面与球面的交集是n - 2维的
其它球面来划分这个球面,相当于把n - 1维区域用m - 1个n - 2维的平面来划分
而n - 2维的这种平面必然是n - 2维的球,因为是球面与球面相交嘛~

每个区域都对应着一个n维区域
最多可以把球面划分成f(n - 1, m - 1)个区域
那么这个球内就有f(n - 1, m - 1)个空间
还要加剩下的球~就是f(n, m - 1)

立即推出:f(n, m) = f(n - 1, m - 1) + f(n, m - 1)

边界条件咱就不说了……YY下就出来了。

至于为啥这是最优的我也不知道……看起来好像很多的样子……考试时我铁定0分……
  评论这张
 
阅读(1053)| 评论(0)
推荐 转载

历史上的今天

评论

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

页脚

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