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

Автор LawlietYagami, история, 8 лет назад, По-английски

I was going through this question which uses DP + Bitmask. But the editorial is too brief to understand and the author assumes everyone's familiarity with DP + Bitmask.

In my understanding,

    for (int i = 1 ; i <= n ; i ++) {
    	for (int k = 1 ; k < 60 ; k ++) {
    		int x = (~fact[k]) & ((1 << 17) - 1);
    		for (int s = x ; ; s = (s - 1) & x) {
                if (dp[i - 1][s] + abs(a[i] - k) < dp[i][s | fact[k]]){
                    dp[i][s | fact[k]] = dp[i-1][s] + abs(a[i]-k);
                }
    		if (s == 0) break;
            }
    	}
    }

We iterate through all the possible values of k , ORing it every time which includes the prime factors in the answer. But why do we add abs(a[i] - k) in the dp, how does it help in identifying the answer? And once the dp matrix is set how do we retrieve the answer? Any help on the problem is appreciated.

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

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

This problem is very well explained in this blog.
To retrieve the answer for any state of your dp you should remember k which you changed a[i] to.
You can see my code for this problem to understand better.

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

    Thanks, now I understand better. Just a last question, for the last row in dp array, the answer is the minimum column which gives the answer, and then you negate the primes marked by bitmask by pos &= (~pr[come[i][pos]]); since the n-1 th answer should have disjoint set of primes, then you retrive the minimum answer for that set of primes from dp array. Is it right or am I missing something?

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

      Yes. dp[n][mask] means that we changed all numbers, used primes from mask and abs(a[1] — b[1]) + ... + abs(a[n] — b[n]) = dp[n][mask]. Our goal is to minimize this value so we choose the mask with minimal dp[n][mask]. And then we retrieve the answer negating primes used in current b[i];