Preliminary knowledge
Bit operations
There are 6 commonly used operators, namely AND (&), OR (|), XOR (^), negation (~), left shift (<<) and right shift (>>)
- The '&' symbol, x&y, will AND the two decimal numbers in binary (both 1 is 1, the rest are 0) and then return their decimal value. For example, 3(11)&2(10)=2(10).
- The '|' symbol, x|y, will OR the two decimal numbers in binary (both 0 is 0, the rest are 1) and return their decimal value. For example, 3(11)|2(10)=3(11).
- The '^' notation, x^y, XORs two decimal numbers in binary (different is 1, remainder is 0) and returns their decimal value. For example, 3(11)^2(10)=1(01).
- ' ~ ' symbol, ~ x, bitwise negation. For example ~101=010.
- '<<' symbol, left shift operation, x<<2, moves each bit of x to the left by two bits in binary, and fills the rightmost part with 0. x<<2 is equivalent to multiplying x by 4.
- The '>>' symbol is a right shift operation.
Some common bit operations
1. Determine whether the i-th bit of a number x in binary is equal to 1.
if( ( (1<<(i−1)) & x ) > 0 )
Principle: 1 is shifted left by i - 1 bit to become 0000010000 (where the i-th bit is the i-th bit). Through AND operation, we can know whether the i-th bit is 1.
2. Change the i-th bit of a number x in binary to 1.
x = ( 1<<( i - 1 ) | x Principle: Shift 1 to the left by i - 1 bit to become 0000010000 (where the i-th bit is the i-th bit). Use the OR operation to know whether the i-th bit is 1.
3. Change the i-th bit of a number x in binary to 0.
x = x & ~(1 << ( i − 1 ) )
Principle: By inverting (1 << ( i − 1 ) ), we get 1111101111 (0 is the i-th bit), and then perform an AND operation to get the number with the i-th bit being 1.
4. Remove the first 1 to the right of a number in binary.
x = x & ( x− 1 )
Principle: Suppose the number x is 11111(2), then x - 1 is 11110(2). The AND operation will remove the last digit of 1, and the number 11110 will be obtained.
If the number x is 11100(2) then x - 1 is 11011(2) and the AND operation yields 11000
Obviously, for a string of binary numbers, the last digit can be divided into two situations: 0/1, and a number can be divided into two front and back parts: the unchanged part + the changing part.
For example: x = 110111(2) can be divided into two parts: 110 111. x - 1 is 110 110
x = 110100(2) can be divided into two parts: 110 100 x - 1 is 110 011
The later changes are implemented by AND operation to remove the first 1 on the right.
Note: There are no requirements for the division method here. 110111(2) can be divided into two parts: 1101 11. The so-called division into two parts is just for the convenience of understanding why the first 1 on the right can be removed. There are other ways of understanding.
Here we only summarize some common bit operations. If you are interested, you can inquire about other operations by yourself.
Overview
State-pressure DP is a DP method that uses the properties of computer binary to describe the state. State pressure is often used in conjunction with BFS and DP.
Use binary numbers to enumerate every possible state, and obtain the optimal solution through the transition of different states.
It can be seen that using binary numbers to describe states can easily cause the number of states to grow exponentially, and the time complexity can easily increase. Optimization can optimize the transfer relationship between different states through conditions, thereby reducing the complexity.
Example explanation:
Knight (P1896 [SCOI2005] Non-aggression) Question description How many placement options are there for placing K kings on an N×N chessboard so that they do not attack each other? The king can attack one grid in each of the eight directions above, below, left, left, right, top, right, and bottom, for a total of 8 grids. Input format There is only one row, containing two numbers N, K (1 <=N <=9, 0 <= K <= N * N) Output format The number of plans obtained Input and output samples input 3 2 output 16
Analysis: Status DP is a DP method that uses the properties of computer binary to describe the state. In this question, a string of binary numbers is used to describe the state of a row.
For example, in a grid with 4 rows and 4 columns, the status of the second row is 1001, which represents the number one in the second row and the fourth one, respectively, which contains a king.
How do we use DP thinking to think about this question?
We know very well that the characteristic of DP is to decompose a large problem into several similar sub-problems, and the solution of the problem has no aftereffects, which means that the decision of this sub-problem will not have an impact on subsequent problem decisions. The characteristic of this question is that there cannot be 1 in the eight directions (1 means there is a king). We can think about it in terms of each row. The status of the row to be solved is determined by the status of the previous row!
Contacting what was said before using a string of binary numbers to represent the status of a row, we can list how many statuses a row can have, and then find how many pairs of statuses can be stacked up and down.
For example:
There are four directions we can move in: up, down, left, and right (this is the status of each row)
There are certain rules for the direction we take:
After walking up, you cannot go down/right (stack of different states)
Doesn’t this look familiar? It’s very similar to an entry-level DP.
Figure 1 Robot path finding
Question link:https://leetcode-cn.com/problems/unique-paths-ii/
The direction of the robot can only be to the right/down. But the direction it can continue to walk after taking one step is random (because the obstacles are random)
Then this question is very simple
In the question, it is required that there cannot be another king in the eight directions of a king. The above bit operations are used, respectively.
x & (x << 1) There is no king in the left and right directions (find all the states of a row)
There is no king in the up and down directions of x & y (determine the up and down directions of the previous row and this row)
x & (y<<1) There is no king in the southeast/northeast direction (determine the southeast/northeast direction of the previous row and this row)
x & (y>>1) There is no king in the southwest and northwest directions (determine the southwest and northwest directions of the previous row and this row)
The state equation is given below:
dp[i][j][k] = dp[i - 1][t][k - total[j]] i stands for 1 - i row j represents the state k represents how many kings are used total represents how many kings are placed in each state The meaning of dp[i][j][k] is a chessboard with rows 1 - i, where the state of the i-th row is the j-th state, and the number of k kings is used
The following requirements are required to complete this question
- How many states are there in the record?
vector<int> kinds;
- Keep track of how many kings each state contains
vector<int> total;
3.dp
vector<vector<vector<long long> > >dp
Record the state and determine how many kings each state contains - using bit operations with prerequisite knowledge
for (int i = 0; i < (1 << n); i++) { //cout << (i << 1)<<endl; if (i & (i << 1))//Judge whether the binary meets the status requirements - whether it contains a king on the left and right continue; else { kind = 0; for (int j = 0; j < n; j++) {//The binary number contains the number of 1's if (i & (1 << j)) kind++; } kinds.push_back(i); total.push_back(kind); } }
dp
//init
//Initialize the state of the first line for (int i = 0; i < kinds.size(); i++) { dp[1][i][total[i]] = 1; } //dp[0][1][0] = dp[0][1][0] = 1; for (int i = 2; i <= n; i++) {//OK for (int j = 0; j < kinds.size(); j++) {//Possible status of each row for (int K = total[j]; K <= k; K++) {Judge that the required k needs to be greater than the number of kings in this row to perform the following operations for (int t = 0; t < kinds.size(); t++) {//Possible status of the previous row if (!(kinds[j] & kinds[t]) && !(kinds[t] & kinds[j] << 1) && !(kinds[t] & kinds[j] >> 1)) dp[i][j][K] += dp[i - 1][t][K - total[j]]; } } } }Optimization ideas:
A state diagram of the transition relationship between different states can be established to simplify the time complexity. For example, the fourth loop can be optimized through the state diagram without traversing all states.
Complete code:
#include<iostream>
#include<vector>
using namespace std;
int n, k;
int main(void) { long long res = 0; int kind = 0; vector<int> kinds; vector<int> total; cin >> n >> k; //init for (int i = 0; i < (1 << n); i++) { //cout << (i << 1)<<endl; if (i & (i << 1)) continue; else { kind = 0; for (int j = 0; j < n; j++) { if (i & (1 << j)) kind++; } kinds.push_back(i); total.push_back(kind); } } //init var vector<long long> arr(k+1,0); vector<vector<long long> >temp(kinds.size(), arr); vector<vector<vector<long long> > > dp(n+1, temp); //dp //init dp for (int i = 0; i < kinds.size(); i++) { dp[1][i][total[i]] = 1; } //dp[0][1][0] = dp[0][1][0] = 1; for (int i = 2; i <= n; i++) { for (int j = 0; j < kinds.size(); j++) { for (int K = total[j]; K <= k; K++) { for (int t = 0; t < kinds.size(); t++) { if (!(kinds[j] & kinds[t]) && !(kinds[t] & kinds[j] << 1) && !(kinds[t] & kinds[j] >> 1)) dp[i][j][K] += dp[i - 1][t][K - total[j]]; } } } } for (int i = 0; i < kinds.size(); i++) { res += dp[n][i][k]; } cout << res; return 0;
}