Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

第100题留念,附上我的思路

Posted by vvinter at 2010-11-16 23:20:00 on Problem 2590 and last updated at 2010-11-16 23:20:32
设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:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator