|
|
вернуться в форумWho can help me!!!tell me how to solve the problem!!! DP:
a[i]:=min(a[i-j*j])+1
j:=trunc(sqrt(i div 4)+1)to trunc(sqrt(i)) can anyone tell me why (sqrt(i div 4)+1)? because there are 4 sides at the square!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!! What does "i" refer to. Can anyone tell me How the above method works. i.e. what a[i] stores. [deleted]
Edited by author 16.12.2008 18:48 thank u very much, i've AC wiht your help how could you get the transition function (a[i]:=min(a[i-j*j])+1)? How could you find it? Is it a "try -error method?" Please explain to me..thanks.. You don't need DP. You can solve it in O(1).
Well actually, O(7) at worst :).
I didn't solve it yet, I have WA at test 5, but I'm sure it can be done.
[Edit] The algo is:
read n
while n>0
x++
n-=(int(sqrt(n)))^2
write x
[/Edit]
P.S: still have WA @ #5 :(. Don't know why...
Edited by author 14.01.2007 23:09 Ok, my bad ... You need DP. Greedy is bad ! I need to remember that... Thanx to the guy who posted the 181 case. Actually, u don't need DP ) didt u read other topics?-) I did, but didn't understand them yet. (yes, I'm still at it after two years!) Greedy fails on 12:
12=9+1+1+1 (greedy)
12=4+4+4 (correct)
Edited by author 15.08.2011 22:30 |
|
|
