MukoiAoi: Don't worry about taking more time in recursion. This is a p-class problem, so I search directly (DP/topology sorting) [code=cpp] #include<iostream> #include<algorithm> #include<set> #include<cstdio> #include<cstdlib> #include<cmath> #include<cstring> using namespace std; #define FOR(i,j,k) for(int i=j;i<k;i++) #define FORD(i,j,k) for(int i=j;i>k;i--) #define LL long long int n,a,b,x; int ff[50]; LL fab(int x) { if (ff[x]) return ff[x]; else if(x%2) ff[x]=fab(x-1)+fab(x-2); else ff[x]=fab(x-1)+fab(x-2)+fab(x-3); return ff[x]; } int main() { cin>>n; FOR(i,0,n) { FOR(i,0,49) ff[i]=0; cin>>a>>b>>x; ff[1]=a; ff[2]=b; cout<<fab(x)<<endl; } } [/code]
