|
|
back to boardHow to solve this problem? Posted by ftc 23 Jan 2007 13:39 I have written a solution with O(n * (m + h) + k * h * h * n * (m + h)) time and O(n * (m + h)) memory, but i can't optimize it to work less than 3.5 seconds. Could somebody give me a hint on better solution? Re: How to solve this problem? Posted by svr 15 Dec 2008 19:00 DP works. Let __int64 F[60][70][3000] is such array that F[i][j][k] number of ways to build tower from level i having at bottom j bricks and k bricks for using. then F[i][j][k]=F[i+1][j-1][k-j]+F[i+1][j+1][k-j]. But here 4200*3000*8 bytes!?. After thinking we find that really in his space used 90000 8-places and 590000 4-places.After this we are using structure int **F[60] as store for 4-places and address for 8-places.If data for DP placed compactly all testes processed quickly. Edited by author 15.12.2008 19:03 |
|
|