State compression DP
skill
Find how many are contained in the binary representation of a number t r u e true true:
int table[16] = {0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4};
int popcount(unsigned int x) {
int ret = 0;
for (int i = 0; i < 8; i++)
ret += table[x & 15], x >>= 4;
return ret;
}
1. Non aggression
Consider composition: 1 ≤ N ≤ 9 1 \leq N \leq 9 1 ≤ N ≤ 9, so according to N N N tectonic pressure d p dp dp, compress the placement of kings in each row
Consider status: array d p [ i ] [ j ] [ k ] dp[i][j][k] dp[i][j][k] stands for the second i i The arrangement of the king in row i is j j In the case of j, it has been placed k k k Kings
Consider transfer: Section i i The king's placement status of line i is affected by i − 1 i - 1 i − 1 line is restricted by the king's placement state, so the second line i i Line i consists of i − 1 i - 1 i − 1 line transfer
Specific method: count the outer layer, and enumerate the second layer respectively in the inner layer i i The placement of line i and i − 1 i - 1 If i − 1 line meets the conditions, it is also necessary to consider i − 1 i - 1 i − the number of Kings placed in line 1 makes a state transition (although the second line i − 1 i - 1 The placement of line i − 1 has been determined, but by the end of i − 1 i - 1 When i − 1 line, the number of Kings placed is uncertain, so make a state transition for all previous situations)
Conditional restrictions:
- Set the first i i The king display status of line i is x x x
- At this point, consider section
i
+
1
i+1
King status of line i+1
y
y
y. In order to avoid attacking each other, that is, to avoid two consecutive diagonals
1
1
1. Two conditions need to be met
- x & ( y < < 1 ) = 0 x \& (y << 1) = 0 x&(y<<1)=0
- x & ( y > > 1 ) = 0 x \& (y >> 1) =0 x&(y>>1)=0
- At the same time, the king of each row cannot be adjacent, that is:
- x & ( x < < 1 ) = 0 x\&(x << 1) = 0 x&(x<<1)=0
- x & ( x > > 1 ) = 0 x\&(x >> 1) = 0 x&(x>>1)=0
- Note that there is another limitation, that is, the number of Kings cannot exceed k k k
- Preprocessing all the placement conditions that meet the conditions can reduce unnecessary enumeration
Sample code (if similar, it is pure plagiarism):
#include <bits/stdc++.h>
using namespace std;
#define int long long
vector<int> vec;
int sum[1 << 10];
int f[20][20][1 << 10];
int n, m;
int getsum(int x) {
int cnt = 0;
while(x) {
cnt += x & 1;
x >>= 1;
}
return cnt;
}
signed main() {
cin >> n >> m;
for(int i = 0; i < 1 << n; i++) {
sum[i] = getsum(i);
if( (i & (i << 1)) or (i & (i >> 1)) or sum[i] > m) continue;
vec.push_back(i);
}
for(auto i : vec) {
f[0][sum[i]][i] = 1;
}
for(int i = 1; i < n; i++) {
for(auto j : vec) {
for(auto k : vec) {
if(j & k) continue;
if(j & (k << 1)) continue;
if(j & (k >> 1)) continue;
for(int s = m; s >= sum[j]; s--) {
f[i][s][j] += f[i - 1][s - sum[j]][k];
}
}
}
}
int ans = 0;
for(auto i : vec) {
ans += f[n - 1][m][i];
}
cout << ans << endl;
return 0;
}
2. Bangbang's chorus stands in line
Consider composition: due to the number of teams 1 ≤ M ≤ 20 1\leq M \leq 20 1 ≤ M ≤ 20, so according to M M M tectonic pressure d p dp dp, compress the order of all teams
Consideration status: because the topic requires that all teams must be adjacent, that is, for a continuous position, we assign a position to each team in turn. The length is the number of people in the team, and the final result is ( 1 ... 1 ... 1 ) 2 (1...1...1)_2 (1... 1... 1) 2 means that all teams have been assigned positions, so
- Construct array f [ i ] f[i] f[i], indicating status i i i, the minimum number of idols listed
- Construct array s u m [ i ] [ j ] sum[i][j] sum[i][j], front i i i locations containing team number j j j number of
- Construct array n u m [ j ] num[j] num[j], No j j j total number of
Consider transitions: for States i i i, if assigned to a number j j j's team position, then [ p o s l , p o s r ] [pos_l, pos_r] [posl, posr] the position of this section should be determined by the team j j j's team members occupy, and the number of people out of the team should be No. in this interval j j The number of people in j can be calculated by prefix and
Example code:
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
const int N = 21, M = 100010;
int f[1 << N], sum[M][N], num[N];
int n, m;
signed main() {
cin >> n >> m;
for(int i = 1; i <= n; i++) {
int x;
cin >> x;
num[x - 1]++;
for(int j = 0; j < m; j++)
sum[i][j] = sum[i - 1][j];
sum[i][x - 1]++;
}
memset(f, 0x3f3f3f, sizeof f);
f[0] = 0;
for(int i = 0; i < 1 << m; i++) {
int length = 0;
for(int j = 0; j < m; j++)
if(i & (1 << j))
length += sum[n][j];
for(int j = 0; j < m; j++)
if(i & (1 << j))
f[i] = min(f[i], f[i ^ (1 << j)] + num[j] - sum[length][j] + sum[length - num[j]][j]);
}
cout << f[(1 << m) - 1] << endl;
return 0;
}
3. Weight weighing
Composition considered: since the number of weights is 1 ≤ N ≤ 20 1 \leq N \leq 20 1 ≤ N ≤ 20, so according to the number of weights N N N tectonic pressure d p dp dp, compress all selected conditions of all weights
Consider the state: since it is required to weigh up to how many kinds of weights can be weighed, we need to list each state that meets the meaning of the question. Once we know which weights to choose, finding the weight that can be weighed is similar to finding the number of schemes in 01 backpack.
Consider transfer: considering that the weight weighed each time is obtained on the basis of the last time, enumerate the existing weight. The second step is i i Whether the number of schemes can be increased after i legal weights are selected is obtained from all the weights weighed before
Specific methods: first, we can use d f s dfs dfs or f o r for All legal states are obtained by enumerating through the for loop, and each legal state needs to be checked once d p dp dp, in d p dp In the dp process, the tag array must be marked first v i s vis vis initialization indicates whether this weight has been obtained. Note: v i s [ 0 ] = 1 vis[0] = 1 vis[0]=1, nothing at first, after all. After that, for the status s t a t e state state to enumerate the number of weights [ 1 , n ] [1, n] [1,n], if s t a t e > > ( i − 1 ) & 1 state >> (i - 1) \& 1 State > > (I − 1) &1 is 1 1 1 indicates that the weight is selected, and then the state can be transferred from all weights.
Reference code:
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
int n, m, ans;
int state[1 << 21], a[30], f[30], vis[2020];
int table[16] = {0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4};
int popcount(unsigned int x) {
int ret = 0;
for (int i = 0; i < 8; i++)
ret += table[x & 15], x >>= 4;
return ret;
}
void dp(int state) {
memset(vis, 0, sizeof vis);
vis[0] = 1;
int tot = 0;
int cnt = 0;
for (int i = 0; i < n; i++) {
if (!(state >> i & 1)) {
for (int j = tot; j >= 0; j--) {
if (vis[j] && !vis[j + a[i + 1]]) {
vis[j + a[i + 1]] = 1;
cnt++;
}
}
tot += a[i + 1];
}
}
ans = max(ans, cnt);
return;
}
int main() {
cin >> n >> m;
for (int i = 1; i <= n; i++)
cin >> a[i];
for (int i = 0; i < (1 << n); i++)
if (popcount(i) == m)
dp(i);
cout << ans << endl;
return 0;
}
4. Artillery positions
Consider composition: due to the number of columns 1 ≤ M ≤ 10 1\leq M \leq10 1 ≤ M ≤ 10, so it is considered to be carried out according to the arrangement of each row d p dp dp, compress the Artillery Force Status of each line
matters needing attention:
- Basic and [non aggression] ([P2704) NOI2001] artillery position - Luogu | new ecology of Computer Science Education (luogu.com.cn) )Same
- This question is enumerated to the third i i At line i, it is also necessary to judge the second line i − 1 i -1 i − line 1 and i − 2 i - 2 Arrangement of i − 2 rows
- At the same time, the status of each line should also be related to the terrain
Example code:
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
int a[1 << 10], n, m, sum[1 << 10], dp[1 << 10][1 << 10][2];
char x;
int getsum(int s) {
int res = 0;
while(s) {
res += (s & 1);
s >>= 1;
}
return res;
}
int main() {
scanf("%d %d", &n, &m);
for(int i = 0; i < n; i++) {
for(int j = 0; j < m; j++) {
cin >> x;
a[i] <<= 1;
a[i] += (x == 'H' ? 1 : 0);
}
}
for(int s = 0; s < (1 << m); s++) {
sum[s] = getsum(s);
if(!((s & a[0]) or (s & (s << 1)) or (s & (s << 2)))) {
dp[0][s][0] = sum[s];
}
}
for(int l = 0; l < (1 << m); l++) {
for(int s = 0; s < (1 << m); s++) {
if(!((l & s) or (l & a[0]) or (s & a[1]) or (l & (l << 1)) or (l & (l << 2)) or (s & (s << 1)) or (s & (s << 2)))) {
dp[l][s][1] = sum[l] + sum[s];
}
}
}
for(int i = 2; i < n; i++) {
for(int l = 0; l < (1 << m); l++) {
if((l & a[i - 1]) or (l & (l << 1)) or (l & (l << 2))) {
continue;
}
for(int fl = 0; fl < (1 << m); fl++) {
if((fl & a[i - 2]) or (fl & (fl << 1)) or (fl & (fl << 2)) or (fl & l)) {
continue;
}
for(int s = 0; s < (1 << m); s++) {
if((s & a[i]) or (s & (s << 1)) or (s & (s << 2)) or (s & fl) or (s & l)) {
continue;
}
dp[l][s][i % 2] = max(dp[l][s][i % 2], dp[fl][l][(i + 1) % 2] + sum[s]);
}
}
}
}
int ans = 0;
for(int l = 0; l < (1 << m); l++) {
for(int s = 0; s < (1 << m); s++) {
ans = max(ans, dp[l][s][(n - 1) % 2]);
}
}
cout << ans << endl;
return 0;
}
5.Corn Fields G
It can be regarded as [non aggression] ([P2704 NOI2001] artillery position - Luogu | new ecology of Computer Science Education (luogu.com.cn) )And Artillery positions Considering the mutual constraints between the terrain and the planting states of two adjacent rows.
Example code:
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
const int N = 20, mod = 100000000;
int f[N][1 << N];
int x[N][N];
vector<int> state;
int main() {
int n, m;
cin >> n >> m;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
cin >> x[i][j];
}
}
for (int i = 0; i < (1 << m); i++) {
if ((i & (i << 1)) or (i & (i >> 1)))
continue;
state.push_back(i);
f[0][i] = 1;
}
for (int i = 1; i < n; i++) {
for (auto j : state) { // Current line status
for (auto k : state) { // Previous line status
if (j & k)
continue;
int flag = 0;
for (int t = 0; t < m; t++) {
if (((j >> t) & 1) == 1 and x[i][t] == 0) {
flag = 1;
break;
}
if (((k >> t) & 1) == 1 and x[i - 1][t] == 0) {
flag = 1;
break;
}
}
if (flag) {
continue;
}
f[i][j] = (f[i][j] + f[i - 1][k] + mod) % mod;
}
}
}
long long ans = 0;
for (auto i : state) {
int flag = 0;
for (int j = 0; j < m; j++) {
if (((i >> j) & 1) == 1 and x[n - 1][j] == 0) {
flag = 1;
break;
}
}
if (!flag) {
ans = (ans + f[n - 1][i] + mod) % mod;
}
}
cout << ans << endl;
return 0;
}
6.No Change G
Consider composition: k ≤ 16 k \leq 16 k ≤ 16, so according to k k k tectonic pressure d p dp dp, compress the state of all coins
Consider status: array p o s [ i ] pos[i] pos[i] indicates i i Which commodity can be purchased for coins in i status, d p [ i ] dp[i] dp[i] indicates status i i Cost under i
Consider transfer: the state of using the current coin must be transferred from the state of using the previous coin
Specific methods: the outer layer circularly enumerates all States, and the inner layer enumerates each coin. If it is used, it will be transferred once. Note that this topic requires that goods must be purchased in turn, so you can use a prefix and maintain the total cost of goods, and then dichotomize the number of the last commodity that can be purchased with the current coin. If you can already buy the second coin at this time n n For n commodities, directly take the minimum value of the cost, and finally judge whether the total amount of all coins is greater than the cost.
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
const int N = 1e5 + 10;
int n, m, pay, money;
long long ans = 0x3f3f3f3f3f;
int coins[N], sum[N];
int pos[1 << 17], dp[1 << 17];
int check(int value, int st) {
int l = st, r = n;
while (l <= r) {
int mid = (l + ((r - l) >> 1));
if (sum[mid] - sum[st - 1] == value)
return mid;
else if (sum[mid] - sum[st - 1] > value)
r = mid - 1;
else
l = mid + 1;
}
return r;
}
int main() {
cin >> m >> n;
for (int i = 1; i <= m; i++) {
cin >> coins[i];
money += coins[i];
}
for (int i = 1; i <= n; i++) {
cin >> pay;
sum[i] = sum[i - 1] + pay;
}
for (int i = 0; i < (1 << m); i++) {
for (int j = 0; j < m; j++) {
if ((i >> j) & 1) {
int last = i ^ (1 << j);
int sum = check(coins[j + 1], pos[last] + 1);
if (sum > pos[i]) {
pos[i] = sum;
dp[i] = dp[last] + coins[j + 1];
}
if (pos[i] == n) {
ans = min(ans, (long long)dp[i]);
}
}
}
}
cout << (money - ans < 0 ? -1 : money - ans) << endl;
return 0;
}