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))

thank u!nou I get AC.

can anyone tell me why (sqrt(i div 4)+1)?

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?-)

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..

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