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

fanhq666的博客

Fan-Fun

 
 
 

日志

 
 

来自cqx的一道dp好题  

2010-10-24 22:00:59|  分类: 程序 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
有2N个人参加舞会,其中N个男生,N个女生,一共要凑成N对(每对一男一女)。现在已知所有人的身高,并且知道
男生比女生矮的对恰有K对。问一共有多少种配对方法。
(1<=N<=100,要求使用高精度)
输入的时候依次输入第i高的同学是男生还是女生(任两人身高不同)

cqx说他认识的能独立做出此题的人只有两个(包含他自己)。

我想出了一个O(N^3)的dp:
设f(i,j,k)表示:前i矮的人中,恰有j个男生比他的partner高,k个女生比她的partner矮的情况下,配对的方法数(可以允许某些人的partner不是前i矮的人,但是每个人必须要决定好到底它比它的partner高还是比它的partner矮)。
转移的方法就是考虑第i高的人到底是决定比它的partner高还是矮,而如果一个男生决定比它的partner高,那么就要
为他在(k-j+1)个候选的女生中挑选一个舞伴。

cqx说这个复杂度的算法是tle的。我经过艰苦卓绝的挤常数(65536进制的高精度和优秀的机器),终于让这个算法在1秒内出解了。

不过这不是长久之计。

cqx告诉了我两个O(N^2)的dp方法:
第一个:
设前i高的男生和前i高的女生配成i对,恰好男高于女的对数是j的情况下的配对方法数是f(i,j)
则f(i,j)可以通过f(i-1,j)、f(i-1,j-1)、f(i-1,j+1)计算出来。
具体计算的方法可让我大伤脑筋。不过,终于是想出来了。
想的过程比较有趣,读者可以自己试试(提示:先编几个身高,然后观察一下f(i,j)和那三项的奇妙的对应关系。)。
第二个:
用dp计算出有j对男生比女生高,其他的对无限制的情况下,配对的方法数f(i)。这一步是可以O(n^2)搞定的。
设g(i)是恰好有i对男生比女生高,其他的对女生比男生高的情况下,配对的方法数。
则:f(N)=g(N)
f(N-1)=g(N)*C(N,1)+g(N-1)
f(N-2)=g(N)*C(N,2)+g(N-1)*C(N,1)+g(N-2)
......
通过解方程的方法就可以依次求出g(N)~g(0)了。

我个人觉得第一个算法比较好想(实际上也不太好想,我就没想出来...),也比较优雅,
而第二个算法的通用性可能好一些(先放宽题目条件,再用排列组合的方法”凝华“)。
cqx比较欣赏算法一(他自己的方法嘛)。
  评论这张
 
阅读(1175)| 评论(2)
推荐 转载

历史上的今天

评论

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

页脚

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