#18962: 加速方法


CSE210617 (A_A)

School : 國立臺中高級工業職業學校
ID : 38161
IP address : [122.116.151.243]
Last Login :
2019-12-02 23:04:57
d255. 11417 - GCD -- UVa11417 | From: [101.137.24.47] | Post Date : 2019-08-18 15:08

用題目提供的雙層迴圈runtime 大概0.3s(C, C++)

 

要加速的話,可以思考看看G(n) 與G(n-1)之間的差異,那就可以用遞迴去解,再另外用一個table去存已知的答案即可

 

int G(int n){
if(table[n]) return table[n];

int ans = G(n-1);
for(){
//計算該層答案...
}
table[n] = ans;
return ans;
}
 
結構大概是這樣,記得建表要初始化為0,另外在初始化一個table[2]的值(G(2) ),如果沒用
 
#18963: Re:加速方法


CSE210617 (A_A)

School : 國立臺中高級工業職業學校
ID : 38161
IP address : [122.116.151.243]
Last Login :
2019-12-02 23:04:57
d255. 11417 - GCD -- UVa11417 | From: [101.137.24.47] | Post Date : 2019-08-18 15:14

用題目提供的雙層迴圈runtime 大概0.3s(C, C++)

 

要加速的話,可以思考看看G(n) 與G(n-1)之間的差異,那就可以用遞迴去解,再另外用一個table去存已知的答案即可

 

int G(int n){
if(table[n]) return table[n];

int ans = G(n-1);
for(){
//計算該層答案...
}
table[n] = ans;
return ans;
}
 
結構大概是這樣,記得建表要初始化為0,另外在初始化一個table[2]的值(G(2) ),如果沒用



結構大概是這樣,記得建表要初始化為0,另外在初始化一個table[2]的值(G(2) ),不然就是要再多加判斷式。

 

這樣的做法實測可以達到7ms~

 
ZeroJudge Forum