1 / 2
Oct 2019

im trying to use dynamic programming in solving this problem but i got TLE . can someone give me hint?
#include
#include
#include <bits/stdc++.h>
using namespace std;
#define endl ‘\n’;
const int MXSIZE = 1e6+6;

int recur(int k, vectorbe , vectorce, int n,int r[]){

int ai=0;
if(r[n]>=0){
return r[n];
}
if(n<=k){
return be[n];
}

for(int i=0;i<n;i++){
ai=ai+ce[i]*recur(k,be,ce,n-i-1,r);
}
r[n]=ai;
return ai;

}

int main(){

int k,b,c,n,total;
cin>>total;
vectorbe;
vectorce;
for(int i=1;i<=total;i++){
be.clear();
ce.clear();

cin>>k;
int copyk=k;
int copyk2=k;
while(copyk–){
cin>>b;
be.push_back(b);
}
while(copyk2–){
cin>>c;
ce.push_back©;
}

cin>>n;
int r[n];
for(int i=0;i<n;i++){
r[i]=-100;
}
int hasil=recur(k-1,be,ce,n-1,r);
int mod=hasil % 1000000000;
cout<<mod<<endl;
}

}

  • created

    Oct '19
  • last reply

    Oct '19
  • 1

    reply

  • 631

    views

  • 2

    users

Just because the problem is defined as a recursive function, doesn’t mean you need to use a recursive function to solve it. An iterative solution would usually be quicker.

The comments suggest a matrix multiplication algorithm may help.

Disclaimer: I’m not solved this, so I may be talking nonsense.

Suggested Topics

Want to read more? Browse other topics in Online Judge System or view latest topics.