Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
Re:直接暴搜过了,没用随机化,利用函数的单调性进行剪枝,见内In Reply To:直接暴搜过了,没用随机化,利用函数的单调性进行剪枝,见内 Posted by:tasty at 2012-08-12 18:51:08 > 设x1,x2,x3....xk为每个字符出现的次数(k<=64) > H可化简为 H=log2(x1+x2+x3+...+xk)-(x1*log2(x1)+x2*log2(x2)+...+xk*log2(xk))/(x1+x2+x3+...+xk); > > 这个函数在 x1>=x2>=x3>=x4>=...>=xk的情况下是单调的,也就是 知道了x1,x2,...xk-1,这个函数就对 xk是单调递增的(偏导>=0),利用这个条件和x1>=x2>=...>=xk这个条件剪枝 就行了. Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator