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

DP Problems(involving printing the optimal items)
Автор mahmoud_arafa, 10 лет назад, По-английски

Hi.

I'm looking for DP problems that involve printing the items that give the optimal answer(involves reconstructing the optimal items), like printing the Knapsack items for example.

If you know any similar problems, please comment with them.

Thanks in advance.

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

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

Problem 1 Problem 2

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

1) Print longest common subsequence of two strings/arrays.

2) Print longest increasing subsequence of an array.(I can do it in O(N^2), can someone tell me how to do it in O(N*logN), please?)

3) http://acm.timus.ru/problem.aspx?space=1&num=1303

4) http://acm.timus.ru/problem.aspx?num=1112

→ Ответить
  • »
    »
    10 лет назад, # ^ |
    ← Rev. 2   Проголосовать: нравится +3 Проголосовать: не нравится
    • Compress the numbers so that they are all in the range 1..N.
    • Build a segment tree that stores the length of the LIS that ends with each number 1..N.
    • Then the pseudocode would be something like this...
    for(int i=1; i<=N; i++)
{
  int lis = query(1, A[i]-1) + 1;
  update(A[i], lis);
}

    If you want to print the actual sequence too, you can also store the node where you "come from" in each node in the tree. The optimum answer will be contained in some leaf of the tree.

    → Ответить