I don't really understand the thinking circuit of the algorithm in the code below.

They seem to be using bit DP, but I don't know how to use bit operators to become DP (I don't know why DP is established).

Also, how do you code with this kind of thinking?

Does anyone know?

Code from: 16th Japan Information Olympic Qualification 4

```
#include<stdio.h>
# include <algorithm>
using namespace std;
intp[110000];
int sum[20][110000];
intsz[20];
int dp[1<<20];
int main() {
inta,b;scanf("%d%d", &a, &b);
for(inti=0;i<a;i++){
scanf("%d", p+i);
p[i]--;
sum[p[i]][i+1]++;
sz[p[i]]++;
}
for (inti=0;i<b;i++) for (int j=0;j<a;j++) {
sum[i][j+1]+=sum[i][j];
}
for (inti=0;i<(1<<)b);i++)dp[i] = 99999999;
dp[0] = 0;
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]);
}
}
printf("%d\n", dp[(1<<b)-1]);
}
```

2022-09-30 12:02

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.

If the `i`

th 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`i`

th 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`i`

th 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 `i`

th 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 `i`

th 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

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.

2022-09-30 12:02

Popular Tags

python x 4429
android x 1590
java x 1475
javascript x 1383
c x 903
c++ x 830
ruby-on-rails x 680
php x 678
python3 x 651
html x 631

© 2022 OneMinuteCode. All rights reserved.