※ 引述《ledia (contemplation)》之銘言：
: ※ 引述《kc655039 (NNN  )》之銘言：
: 的確不是很容易看 ^^;
: 在還沒看完你的程式碼之前
: 說實在我也不太知道該怎麼幫你的程式加速
: 不過我自己寫這題的經驗上看來
: 或許你是多做了太多重覆的事情
: 因為我的程式用了 1.820 秒(雖然也不少了), 而這題限 10 秒
過了也差不多有半年了,最近又開始寫這題,想說也過了半年了....之類的,
跟上回用的方法一樣,可是發現遞迴似乎可以用一下,所以就用了,想說搞不
好會有令人高興的結果,一開始還是TLE,TLE了滿多次不管我怎麼改都一樣,
後來發現....是因為下面紅色字的地方本來是零,Backtracking(...)的參數
本來也沒有k,改成現在這樣以後就很快的AC了(0:00:340),然後其實之前就
想說如果第一個或是其中有一個沒辦法構成邊其實就是no了,所以就一開始
就放存放邊的array的第一個元素進去,這樣就可以減少遞迴樹的size,
改了這樣以後就變成0:00:076,後來又想,如果由小到大排列,這樣的話,
如果加上某邊然後就大於邊長,那後面的邊都可以不用試了,也可以減少遞迴
的次數,所以我就上了,可是還是0:00:076....是因為排列把時間拖回來了嗎??
還是排列的時機不對之類的,所以目前就這樣了...我似乎想不出加速的方法了,
不過真的令我滿驚訝的,想不到把紅字的地方做那樣的改變會差那麼多.....
還是有點搞不懂...是哪種側資會差到從TLE到000340.....
對了請你把你的code寄給我好嗎 655039@ms57.url.com.tw 我想多看看,
下面是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)