|
|
вернуться в форумI wonder why somebody passed it only used less than 0.1 sec ! Послано XueMao 9 апр 2003 17:19 I used DP , 0.8 sec , but some people only used 0.04 sec and uesd less than 100K memory ! why ? How can they do it ? can anybody tell me ? It can be done in O(n^2) (-) > I used DP , 0.8 sec , but some people only used 0.04 sec and uesd > less than 100K memory ! why ? How can they do it ? can anybody tell > me ? Re: It can be done in O(n^2) (-) how? i managed a 0.09 O(n^3) but how do u do n^2?? i might have an N^2 ideea but it n^2 memory...... Re: It can be done in O(n^2) (-) X[i]: how many black horses are in the first i horses Y[i]: how many white horses are in the first i horses We use Dp. F[i,j] = min { F[i-1,k] + (X[j]-X[k])*(Y[j]-Y[k]) } | K<J The answer is F[K,N]. Suppose F[i,j] get the minimal value when k=k0. Let W[i,j]=k0. You can prove : w[i,j-1]<=w[i,j]<=w[i+1,j] So you can solve this problem in o(n^2). Re: It can be done in O(n^2) (-) Sorry, could you explain please what's k0? |
|
|