Understanding Bit DP Thinking Circuits

Understanding DP Gradualization Formula

Let's forget about bit DP and think about normal DP.As stated in the explanation

dp[S]: = (minimum number of stuffed toys that need to be taken out so far when the set of types used for placement is S)

Yes, considering adding a new stuffed toy j to S,

dp[S {{j}]=min(
             the minimum value if the state S {{j} is reached in the other order, 
             Minimum value to reach state S (=dp[S]) + ((Number of stuffed toys included in S + 1) Number of stuffed toys included (Number of stuffed toys j) Number of stuffed toys not included in j)
            )

It can be calculated like this.Finally, dp [set including all stuffed toys] will be solved.

However, array subscripts must be integers, so you need a way to match integers to a set.

How to represent a set as an integer

If the ith element is included, the set can be represented as an integer with a prominent i bit.Operations on a set can also be expressed in bit operations.

The following is an example of a set operation (where n, m is an integer (representing a set).

• empty set...0
• n and the sum set of m...n|m
• n and m product set...n&m

• n contains the ith element...(n&(1<<(i-1))!=0)

  Applications of product sets. 1<<(i-1) represents a set that only has the i bit, i.e., contains only the ith element, so you can take the product from the original set and make sure it is not an empty set.

• A set containing all elements from 1 to b...(1<b)-1

  1<b displays only the b+1st bit.Subtract 1 from now to make all lower b bits 1

n contains the ith element...(n&(1<<(i-1)))!=0)

Applications of product sets. 1<<(i-1) represents a set that only has the i bit, i.e., contains only the ith element, so you can take the product from the original set and make sure it is not an empty set.

A set containing all elements from 1 to b...(1<b)-1

1<b displays only the b+1st bit.Subtract 1 from now to make all lower b bits 1

About Bit DP

Now that the set is represented by an integer, it can be used as an adjunct to an array.This is the bit DP mentioned in the commentary, and the code is as follows:

 for (inti=0;i<(1<<;)b);i++){
    int pos = 0;
    for(int j=0;j<b;j++) if(i&(1<<j))pos+=sz[j];
    for(int j=0;j<b;j++){
        if(i&(1<<j)) continue;
        dp[i+(1<<j)] = min(dp[i+(1<<j), dp[i]+sz[j]-sum[j][pos+sz[j]]+sum[j]);
    }
}

In the code above, i corresponds to the set, which moves from 0 to (1<b)-1 (=b digit 1) to list all subsets of "b stuffed animal sets."

Next, let's look at the inner for.

for(int j=0;j<b;j++)if(i&(1<<j))pos+=sz[j];;

In , we have added the number of stuffed toys j to pos that are included in the set i.In other words, we calculate the number of stuffed toys that i includes.

The following for is the core of the DP, but j represents a stuffed animal.It moves from 0 to b-1, enabling processing for individual stuffed animals.

for(int j=0;j<b;j++){
    if(i&(1<<j)) continue;
    dp[i+(1<<j)] = min(dp[i+(1<<j), dp[i]+sz[j]-sum[j][pos+sz[j]]+sum[j]);
}

First of all, if the set i already contains stuffed toys j, skip it.The rest is the calculation part of dp[S {{j}] written above.If you know how to use cumulative sum, you will understand it.

By the way, the good thing about this bit DP is that S<=S {{j} is established when the set is expressed as an integer.In the code above, i was simply increased from zero, but when you calculate dp[S {{j}], dp[S] is required, so it is convenient for you.

This is difficult, but bit DP itself is a well-known technique, so I think this technique will be mentioned as a candidate, especially when the condition is small.