Wrong Answer on DP code (C++)

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

Автор DragonFruit, 11 лет назад, По-английски

why my code is wrong?

9871305

thank you

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

wrong answer, dp, ????????

DragonFruit
11 лет назад
7

Комментарии (7)

Написать комментарий?

Bayan

11 лет назад, скрыть # |

← Rev. 4 →

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.

→ Ответить

DragonFruit

11 лет назад, скрыть # ^ |

thanks a lot...

I should learn one that you said

→ Ответить

DragonFruit

11 лет назад, скрыть # ^ |

I didn't find anything can you help me?

→ Ответить

Bayan

11 лет назад, скрыть # ^ |

← Rev. 2 →

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://mirror.codeforces.com/contest/474/submission/9871904

→ Ответить