Блог пользователя DragonFruit

Wrong Answer on DP code (C++)
Автор DragonFruit, 10 лет назад, По-английски

why my code is wrong?

9871305

thank you

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

  • Проголосовать: нравится
  • +3
  • Проголосовать: не нравится

»
10 лет назад, # |
← Rev. 4   Проголосовать: нравится 0 Проголосовать: не нравится

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.

→ Ответить
  • »
    »
    10 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    thanks a lot...

    I should learn one that you said

    → Ответить
  • »
    »
    10 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    I didn't find anything can you help me?

    → Ответить
    • »
      »
      »
      10 лет назад, # ^ |
      ← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

      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.me/contest/474/submission/9871904

      → Ответить
»
10 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Why you are creating new accounts

→ Ответить