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

Help In Question B. BerSU Ball ( Codeforces Round #277.5 )
Автор -______-, история, 6 лет назад, По-английски

I've successfully solved this problem using Greedy Approach but in the editorial it was given that the probelm can also be solved using Dynamic Programming.

Can someone help me with the DP solution ? (preferably in C++)

Problem Link : http://codeforces.com/problemset/problem/489/B

Editorial Link : http://codeforces.com/blog/entry/14741

My Solution ( Greedy ) : 39216236

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

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

First, sort arrays a and b.

Let dp[i][j] be the answer if we have only a[0..i] and b[0..j].

dp[i][j] is maximum of:

  • 0
  • 1 if |a[i]-b[j]|<=1
  • dp[i-1][j-1]+1 if i-1>=0, j-1>=0 and |a[i]-b[j]|<=1
  • dp[i-1][j] if i-1>=0
  • dp[i][j-1] if j-1>=0

Answer will be dp[n-1][m-1].

My Solution: 39227258

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

    Can we do an O(n) dp ?

    Can we solve the problem Online (without brute-forces) ?

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

    Here is my shorter dp solution O(n * m) ~ vector dp(n + 1, vi(m + 1, 0)); for (int i = 1; i <= n; ++i) for (int j = 1; j <= m; ++j) dp[i][j] = max({dp[i-1][j], dp[i][j-1], dp[i-1][j-1] + (abs(boy[i-1] — girl[j-1]) <= 1)}); ~

    Can we dp in O(n) if we use frequency array ?

    → Ответить