在吃了接近十個NA之後

第三點地測資卻出現TLE

目前已經改掉了遞迴的算法

不知道有沒有更快的？

程式碼：

#include <cstdlib>
#include <iostream>

using namespace std;

long long int a,c[1000000],d[1000000];

long long int f(long long int n){
long long int i;   
if(n==1)return 1;
else {
   c[1]=1;
   for(i=2;i<=n;i++){
       c[i]=c[i-1]+i;                 
   }
}
return c[n];   
}
long long int g(long long int m){
long long int j,k;
if(m==1)return 1;
else {
   c[1]=1;
   for(j=2;j<=m;j++){
       d[1]=1;
       for(k=2;k<=j;k++){
           d[k]=d[k-1]+k;                 
       }
      
       c[j]=c[j-1]+d[j];                 
   } 
}
return c[m];   
}

int main(int argc, char *argv[])
{
   
    while(cin>>a){
                        
       cout<<f(a)<<" "<<g(a)<<endl;             
    }
   
   
    system("PAUSE");
    return EXIT_SUCCESS;
}

謝謝

system("pause"); 建議拿掉! 因為cin幫你判斷EOF 才不會出問題!

另外，你這樣每次輸入都要重新建表一次! 當然TLE!

建議建表一次就好，到他的最大值( 30000 )

輸入時就輸出表內的值即可

聽了高人的指點

我將程式碼修改了

但第一次建表卻花費了太多的時間

讓我三點測資都TLE了...

程式碼：

#include <cstdlib>
#include <iostream>

using namespace std;

long long int a,c[30000],d[30000],e[30000];

void f(){
long long int i;   
c[1]=1;
for(i=2;i<=30000;i++){
    c[i]=c[i-1]+i;                 
}
//cout<<c[1]<<endl;
   
}
void g(){
long long int j,k;
d[1]=1;
for(j=2;j<=30000;j++){
    e[1]=1;
    for(k=2;k<=j;k++){
        e[k]=e[k-1]+k;                 
    }
    d[j]=d[j-1]+e[j];                 
}
//cout<<d[1]<<endl;
}
   

int main(int argc, char *argv[])
{
    f();
    g();
    while(cin>>a){
      
       /*b=a;
       y=1;
       x=1;
       while(a!=1){
          x+=a;
          a--;        
       }
          if(b==1)y=1;
          else {
             c[1]=1;
             for(j=2;j<=b;j++){
                d[1]=1;
                for(k=2;k<=j;k++){
                    d[k]=d[k-1]+k;                 
                }
                               
                c[j]=c[j-1]+d[j];                 
             } 
          y=c[b];
          }*/
             
                 
     cout<<c[a]<<" "<<d[a]<<endl;             
   }
    
    
        return EXIT_SUCCESS;
}

如果將30000調小就會WA

看來還必須在驗算法部分多多請教了

謝謝

(system pause是忘記刪掉的)

其實不需要建表，只用迴圈就可以將時間壓下去了(幾ms就可以完成)。
利用的是稍微化簡公式：

因為f(n) = n + f(n-1)，
　　f(1)=1
　　f(2)=2+f(1)
　　f(3)=3+f(2)
　　       :
　　       :
　　       :
＋　f(n)=n+f(n-1)
__________________
　　f(n)=1+2+3+...+n    (左右對消)
　　　　=n(n+1)/2

也就是說f(n)可以輕易算出，至於g(n) = f(n) + g(n-1)，利用遞迴關係展開如下：
g(n)=f(n)+[ f(n-1)+g(n-2) ]
　　=f(n)+f(n-1)+[ f(n-2)+g(n-3) ]
　　　　　　　　：
　　　　　　　　：
　　　　　　　　：
　　=f(1)+f(2)+f(3)+...+f(n)

於是使用下面這段程式碼就可以符合時間要求了

#include<iostream>
using namespace std;

long long fsum(int n){
    long long output=0;
    for(int i=1;i<=n;i++){
        output+=(i*(i+1)/2);
    }
    return output;
}

int main(){
int a;
while(cin>>a){
    cout<<(a*(a+1)/2)<<" "<<fsum(a)<<endl;
}
}
 

ps.可以應用Sigma公式列出通式 g(n)=n(n+1)(n+2)/6，將程式碼更精簡，試試吧！