※ 引述《ledia (contemplation)》之銘言： : ※ 引述《kc655039 (￾NN￾N ￾  )》之銘言： : 的確不是很容易看 ^^; : 在還沒看完你的程式碼之前 : 說實在我也不太知道該怎麼幫你的程式加速 : 不過我自己寫這題的經驗上看來 : 或許你是多做了太多重覆的事情 : 因為我的程式用了 1.820 秒(雖然也不少了), 而這題限 10 秒 過了也差不多有半年了,最近又開始寫這題,想說也過了半年了....之類的, 跟上回用的方法一樣,可是發現遞迴似乎可以用一下,所以就用了,想說搞不 好會有令人高興的結果,一開始還是TLE,TLE了滿多次不管我怎麼改都一樣, 後來發現....是因為下面紅色字的地方本來是零,Backtracking(...)的參數 本來也沒有k,改成現在這樣以後就很快的AC了(0:00:340),然後其實之前就 想說如果第一個或是其中有一個沒辦法構成邊其實就是no了,所以就一開始 就放存放邊的array的第一個元素進去,這樣就可以減少遞迴樹的size, 改了這樣以後就變成0:00:076,後來又想,如果由小到大排列,這樣的話, 如果加上某邊然後就大於邊長,那後面的邊都可以不用試了,也可以減少遞迴 的次數,所以我就上了,可是還是0:00:076....是因為排列把時間拖回來了嗎?? 還是排列的時機不對之類的,所以目前就這樣了...我似乎想不出加速的方法了, 不過真的令我滿驚訝的,想不到把紅字的地方做那樣的改變會差那麼多..... 還是有點搞不懂...是哪種側資會差到從TLE到000340..... 對了請你把你的code寄給我好嗎 [email protected] 我想多看看, 下面是code應該比以前那個好看滿多百倍的了吧.是沒有排序的. 不過好像還是滿難看的所以加了些註解,遞迴樹的size好像決定了速度?? 還有就是我有用到一個全域變數judge那個可以不用嗎,因為有時候用遞迴, 都會用全域變數,我在想說有沒辦法完全不要用這樣. #include <iostream> using std::cout; using std::cin; using std::endl; int judge; void Backtracking(int k,const int length,int n,int data[][20],int total,int accumulator) { int i; if (accumulator>length) return; if (total==3) { judge=1; return; } if (accumulator==length) { for (i=0;i<n;i++)//這個主要是放下一個邊的第一個元素 if (data[1][i]) { data[1][i]--; Backtracking(i,length,n,data,total+1,data[0][i]); data[1][i]++; break; } return; } for (i=k;i<n;i++) { if (data[1][i]) { data[1][i]--; Backtracking(i,length,n,data,total,accumulator+data[0][i]); if (judge) break; data[1][i]++; } } } main() { int N; int n; int data[2][20];//存放資料的地方上層是存邊長,下層存有幾個這個長度 //的資料 int length; //邊長 int i,j,temp,counter,yes; cin>>N; while (N) { length=0; judge=0; counter=0; yes=0; cin>>n; for (i=0;i<n;i++)//這個迴圈主要用來輸入資料,順便整理 { cin>>temp,length+=temp; for (j=0;j<counter;j++) if (temp==data[0][j]) { data[1][j]++; break; } if (j==counter) data[0][counter]=temp,data[1][counter++]=1; }//counter是資料的數量 if (length%4==0) { length/=4;//算一下一個邊多長這樣 for (i=0;i<counter;i++)//看看有沒有輸入的資料大於邊長 if (data[0][i]>length) { yes=1; break; } if (!yes) { data[1][0]--; Backtracking(0,length,counter,data,0,data[0][0]); } } if (judge) cout<<"yes"<<endl; else cout<<"no"<<endl; N--; } return 0; } --

※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 218.161.12.54 ※ 編輯: kc655039 來自: 218.161.12.54 (02/19 21:05)