SPOJ — NUMTSN — 369 Numbers

Revision en5, by tortuga, 2015-10-08 22:45:17

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 \ //

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);

}

Tags dynamic programming, spoj, digit dp

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en6 English tortuga 2015-10-08 22:46:17 6 Tiny change: '\\\n//\n\n\nint dp[5' -
en5 English tortuga 2015-10-08 22:45:17 1058
en4 English tortuga 2015-10-08 22:43:12 19
en3 English tortuga 2015-10-08 22:42:37 2
en2 English tortuga 2015-10-08 22:42:14 762
en1 English tortuga 2015-10-08 22:41:22 2804 Initial revision (published)