I am trying to solve this problem http://www.spoj.com/problems/NUMTSN/ on spoj. I tried to use dynamic programming. I am getting TLE. Here is my code: http://ideone.com/VnPIZp \ //
//code int dp[54][2][18][18][18];
int solve(int index, int free, int t,int s, int n) { if(t > 17 || s > 17 || n > 17) return 0;
//DBG(index);
if(index == num)
{
//DBG(index);
if(t >= 1 && (t == s) && (s == n))
return 1;
return 0;
}
int &ret = dp[index][free][t][s][n];
if(ret != -1) return ret;
ret = 0;
int nfree,nt,ns,nn;
for(int i = 0; i < 10; i++)
{
nfree = free | (i < a[index]);
nt = t + ( (i == 3) ? 1 : 0); //DBG(nt);
ns = s + ( (i == 6) ? 1 : 0); //DBG(ns);
nn = n + ( (i == 9) ? 1 : 0); //DBG(nn);
if(free)
{
ret = ((ret % MOD) + (solve(index+1, nfree, nt, ns, nn)) % MOD) % MOD;
}
else
{
if( i <= a[index])
ret = (ret % MOD + (solve(index+1, nfree, nt, ns, nn)) % MOD ) % MOD;
}
}
return (ret% MOD);
}