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

DP problem

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

http://mirror.codeforces.com/problemset/problem/31/E can any one explain how to solve this problem i am very weak in dp ? how to think plz explain it fully (sorry for my poor english )

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

»
12 лет назад, # |
  Проголосовать: нравится -7 Проголосовать: не нравится

Homer has a C(2n,n) different ways to get his digits,since n<=18 you can try all possible ways and choose the best.

dp in not necessary in this problem.

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

    Hello, As far as I know C(36, 18) is almost 90*10^8 so if you try all possible ways it'll take around 90 seconds!

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

You know that both players will take n digits, so if Homer takes digit D and it's the Kth digit he takes, the ACTUAL value of that digit will be 10^(n — K) * D.

For example, for the number 9911, Homer takes digits 9 and 1. The actual value of that 9 he takes is 90, because he takes it first. If he took, let's say, digits 852, the actual value of the first 8 would be 800, the 5 would be 50 and the 2 would be 2.

With that knowledge, we can go through the digits from left to right and make a DP solution.

Let F(d,h) be the best state when Homer takes h digits and the last digit we processed is the digit in position d. We have two cases, either Homer took the digit d, or he didn't.

So F(d,h) = max(F(d-1, h-1) + 10^(n — h) * x, F(d-1, h) + 10^(n — d — h) * x), where x is the digit at position d.

We have to keep track of which of these two cases we came from for each state to be able to reconstruct the movements in the end and print them out.

Here's my submission: 2956565

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

    @diego_v1 very helpful :)

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

    Just a little correction for those who don't like looking at codes and have just read your explanation:

    The 2 values that you compare are F(d-1, h-1)+10^(n-h)*x and F(d-1,h)+10^(n-_**(d-h)**_). <- The brackets in bold were missing. It's not such big a problem if you actually think when you are writing the code and you are not just copying this formula. Anyways, great explanation with all the examples and stuff! :)

    → Ответить