|
|
Показать все ветки Спрятать все ветки Показать все сообщения Спрятать все сообщения | What is DP? | Alexey Procenko | 1073. Квадратная страна | 16 дек 2007 10:17 | 6 | Help me please. I don't understand what DP is. Any hints? DP is method when next element depend from previous for this problem you have to build array A in which A[i] content minimum count of squares for i area Else its abbreviation of dynamic programming. Thanks! I think it might help. I have reviewed all posts in this topic but i still can't solve this problem. Does anybody can explain it to me in more detail? Mail me, and I'll explain it in Russian. :) ushal@list.ru Edited by author 16.12.2007 10:18 | If you use DP | PSV | 1073. Квадратная страна | 2 дек 2007 18:13 | 4 | Firstly it's comfortable to use recursive scheme of DP. Secondly : I've STAK_OVERFLOW when tried to take DP form 1 to sqrt(n), but AC when sqrt(n) downto 1. I don't know what's the differnce but result depend of it I think, you don't need DP in this problem. It can be solved with simple O(n^1.5) algorithm. would you please further explain the O(n^1.5) and non-DP approach? Thanks, i don't know why it is not dp, but i think he was mentioned BFS | Help Why WA | yuxiaolei | 1073. Квадратная страна | 1 дек 2007 15:42 | 2 | //1073 #include<iostream> #include<cmath> using namespace std; unsigned long mn; bool fine; unsigned long sch(unsigned long n,unsigned long stpos,unsigned long time) { if ((fine==true)&&(time==mn-1)){ return(1); }else{ n=n-stpos*stpos; if (n==0) { fine=true; return(1); }else{ if (n<(stpos*stpos)) { stpos=int(floor(sqrt((long double)n))); } unsigned long submn,i,tmp; submn=sch(n,stpos,time+1); for (i=stpos-1;i>0;i--) { tmp=sch(n,i,time+1); if (tmp<submn) { submn=tmp; } } return(submn+1); } } } int main (void) { unsigned long n,rtfn; cin>>n; if (n==0) { cout<<0; return 0; }else{ fine=0; rtfn=int(floor(sqrt((long double)n))); cout<<sch(n,rtfn,0); } } I think some tests for you will be good; for N=50000 answer is 2(explanation 1 piece 200*200 and the other 100*100) N=0 0; N=1 1 | i din't | zzzlll | 1073. Квадратная страна | 25 сен 2007 12:15 | 2 | who can explain it for me??? In my opinion,the sentense " minimize an amount of pieces he buys"is very important,just make the pieces of the land the least,use DP,I think you can solve in!Good luck! | please help.. why I have compilation error?? | Felipe Guilhon | 1073. Квадратная страна | 12 авг 2007 16:50 | 2 | the only part that I can think of getting compile error is this: int num; int tmp; tmp = (int) sqrt(num); But why?? Write tmp = (int) sqrt((double)num)(p.s. read FAQ) | Help, why I have Compillation Error? | sas | 1073. Квадратная страна | 3 май 2007 21:50 | 3 | #include <iostream> #include <math.h> using namespace std; long int c,i,a,s; int main () { cin>>a; s=0; for(;;) { s++; a-=pow(int (sqrt(a)),2); if(a==0) break; } cout<<s<<endl;
return 0; } a-=pow(int (sqrt(a)),2); -> a-=(int)pow(int (sqrt((double)a)),2.0); Edited by author 03.05.2007 21:56 Error here: a-=pow(int (sqrt(a)),2); you must write a-=pow(int (sqrt((double)a)),2); P.S. your algorithm gives WA#5! Edited by author 03.05.2007 21:51 Edited by author 04.05.2007 01:48 | test 3 | IOANNIS | 1073. Квадратная страна | 27 ноя 2006 04:03 | 1 | test 3 IOANNIS 27 ноя 2006 04:03 No problem, I solved it in 0.001s Edited by author 27.11.2006 04:11 Edited by author 27.11.2006 05:02 Edited by author 27.11.2006 05:02 | Test 5 | Mike | 1073. Квадратная страна | 1 окт 2006 04:20 | 2 | Author: Test 5 -- Wrong answer Correct -- 2: 2^2+1^2 Why Error Edited by author 23.09.2006 02:26 check test 181: correct answer is 2: 10^2+9^2. | Did I misunderstood -_-a WA Test 5 | rakker | 1073. Квадратная страна | 13 авг 2006 13:34 | 5 | connect to question: why? close connection :) author, check test 181: correct answer is 2: 10^2+9^2. any ideas about the algorythm? I used DP but it's tle-ing on #6 :( any ideas about the algorythm? I used DP but it's tle-ing on #6 :( Try to do some improvements to your DP. You don't need to do complete DP. I used DP with recursion. At first it got TLE#5. First improvement led to TLE#6. Second improvement - TLE#11. Finaly after last improvement I got AC in 0.703sec and 146KB But another, better algorithm exists ;) |
|
|
|