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 |
第100题留念,附上我的思路设f(k)是走k步能达到的最长距离。 则: f(0)=0;f(1)=1;f(2)=2 f(n)=max{f(n-1)+1, f(n-2)+n} (n>=3) 从k=3开始由小到大求f(k),直到f(k)>=N,输出k。N为输入两个数的差。 由于上面递推式的解大概是k^2的多项式,所以算法复杂度为O(N^0.5),对于N<=2^31来说是可以接受的。 Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator