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

Nice DP Problem
Автор jhjfbsbfkbjfnfnfjfj, история, 6 лет назад, По-английски

I have studied about finding LIS (longest increasing subsequence) How do I extend that knowledge to find LIS where gcd(xi, xi+1) > 1? Please help me here is the link to the question https://mirror.codeforces.com/problemset/problem/264/B

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

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

Hint : The problem is related to prime factors. # of prime factors of $$$a_i$$$ is small.

Another hint
DP hint
→ Ответить
  • »
    »
    6 лет назад, скрыть # ^ |
     
    Проголосовать: нравится 0 Проголосовать: не нравится

    you mean this dp would work dp[i] = dp[i] + 1. where i is one of the primefactors of ith number. right? if yes then the maximum value of this array will be our answer?

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

      No, (1) all dp[i] must be replaced with (2) (max of all dp[i])+1 where i is one of the primefactors. For example, when a=6, replace dp[2] and dp[3] with max(dp[2],dp[3])+1. This is because (1)[6 is a multiple of 2 and a multiple of 3], and (2)[we can put 6 after a multiple of 2 or a multiple of 3]. However, "max of dp array will be our answer" is right.

      /* If you need, see my submission. */ Sorry my submission isn't fit the explanation.

      → Ответить