DragonFruit's blog

Wrong Answer on DP code (C++)
By DragonFruit, 9 years ago, In English

why my code is wrong?

9871305

thank you

UP: I changed my code to this but i have wrong answer now too: 9871785

  • Vote: I like it
  • +3
  • Vote: I do not like it

»
9 years ago, # |
← Rev. 4   Vote: I like it 0 Vote: I do not like it

You will have TLE because T<=10^5 and b<=10^5 , your solution is O(T*(b-a)*(your recursion)).
You have WA because you should add here

            mem[x]+=dp(x-1);
            if(x>=k)
                mem[x]+=dp(x-k);

this mem[x] %= MOD;
Use precalc to solve it.

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    thanks a lot...

    I should learn one that you said

    → Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I didn't find anything can you help me?

    → Reply
    • »
      »
      »
      9 years ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      Firstly we try change your recursive dp for linear (and we will pre calculate("precalc" or "pre calc") result in array to find next time by O(1)). 

      for (int i=1;i<=100000;i++){
        d[i]=d[i-1];
        if (i-k>=0)d[i]+=d[i-k];
        d[i]%=INF;
}

      Now we can find fastly your dp(x) by d[x]
      After this we must to find sum of all elements from d[a] to d[b]
      we can do it by create a new array that will have
      all sum from 1 to i(sum[i]=d[1]+...+d[i]) by precalc 

      for (int i=1;i<=100000;i++){
    sum[i]=sum[i-1]+d[i];
}

      then we know that answer for sum from a to b like this cout<<sum[b]-sum[a-1];
      You can look for my code http://codeforces.com/contest/474/submission/9871904

      → Reply
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Why you are creating new accounts

→ Reply