红魔咖啡馆

头发越掉越多，头发越掉越少

0%

【动态规划】状压DP

发表于 分类于 ，
本文字数： 7.1k 阅读时长 ≈ 13 分钟
介绍了子集枚举，状压DP的思想与例题

子集枚举

给定一个包含n个元素的数组a，子集枚举就是枚举数组a的所有子集，每个元素有选和不选两种状态，故可以用二进制来表示

故我们可以用一个n位二进制数mask，若第i位为0，则表示不选第i个元素，若第i位为1，则表示选第i个元素

模板

1
2
3
4
5
6
7
for (int mask = 0; mask < (1 << n); mask++) {
    for (int i = 0; i < n; i++) {
        if (mask & (1 << i)) {
            // 选中了 a[i]
        }
    }
}

其中，mask表示当前子集的二进制状态，从0到\(2^n-1\)

则第三行表示第i个元素是否被选

例

小红拿到了一个长为n的数组 \(a=\{a_1,a_2,\cdots,a_n\}\)，她要从中取若干个元素，使得这些元素的和恰好为 k。 现在小红想知道，有多少种不同的合法取数方案，请你帮帮她。

Code：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
void solve() {
    ll n;
    ll k;
    cin >> n >> k;
    vector<ll> arr(n+1);
    for (int i = 1; i<=n; i++)
    {
        cin >> arr[i];
    }
    ll cnt = 0;
    for (int i = 1; i<(1ll<<n); i++)
    {
        ll sum = 0;
        for (int j = 1; j<=n; j++)
        {
            if(i&(1ll<<(j-1)))
            {
                sum+=arr[j];
                if (sum>k) break;
            }
        }
        if (sum==k) cnt++;
    }

    cout << cnt << endl;

}

状压DP

状态转移时，数组形式的可变参数不方便修改（如数组中某个元素是否被使用），我们可以用整数位信息来表示某个样本能否还能使用，并利用这个信息进行尝试，进而进行动态规划

若有k个样本，则有\(2^k\)个状态

注意，状压dp能解决的问题一般数量都不大，在20个以内

例1-我能赢吗

状压dp的递归版本，通过传递st来表示选或不选

题中有两个可变参数：st与rest，但只需要对st作缓存，rest是被st决定的

即只需要关注最关键的可变参数，被决定的不需要管

dp表的含义：

  • dp[st]==0代表没算过
  • dp[st]==1代表算过，答案是true
  • dp[st]==-1代表算过，答案是false

递归函数f的含义：

在数字范围1-n的情况下，当前先手面对st的数字状态，在累加和还剩rest的情况下返回先手能不能赢

能赢返回true，不能返回false

时间复杂度：\(O(n*2^n)\)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
 bool canIWin(int n, int m) {
    if (m==0) return true;
    if (n*(n+1)/2<m) return false;
    vector<int> dp((1<<(n+1)));
    return f(n, (1<<(n+1))-1, m, dp);
}
bool f(int n, int st, int rest, vector<int> &dp)
{
    if (rest<=0) return false;
    if (dp[st]!=0) return dp[st]==1;

    bool flag = 0;
    for (int i = 1; i<=n; i++)
    {
        if ((st&(1<<i))&&!f(n, (st^(1<<i)), rest-i, dp))
        {
            flag = 1;
            break;
        }
    }
    dp[st] = flag?1:-1;
    return flag;
}

例2-火柴拼正方形

同样只需要对st做缓存，cur和re都是随着st变化的

f函数里，每次选择一条边，提前算好正方形每条边的长度，用cur计算目前累计的长度

若cur加上下一条边刚好是需要的长度，就重新计算下一条边，re（需要的边数）-1

否则就继续累加当前边数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
bool makesquare(vector<int>& matchsticks) {
   int sum = 0;
   for (auto it: matchsticks)
   {
    sum+=it;
   } 
   if (sum%4) return false;

   int n = matchsticks.size();
   vector<int> dp((1<<n)+1);
   return f(matchsticks, sum/4, (1<<n)-1, 0, 4, dp);


}
bool f(vector<int> nums, int len, int st, int cur, int re, vector<int> &dp)
{
    if (st==0)
    {
        return re==0;
    }
    if (dp[st])
    {
        return dp[st]==1;
    }
    bool flag = 0;
    for (int i = 0; i<nums.size(); i++)
    {
        if ((st&(1<<i))&&cur+nums[i]<=len)
        {
            if (cur+nums[i]==len)
            {
                flag = f(nums, len, st^(1<<i), 0, re-1, dp);
            }
            else
            {
                flag = f(nums, len, st^(1<<i), cur+nums[i], re, dp);
            }
            if (flag) break;

        }
    }
    dp[st] = flag?1:-1;
    return flag;
}

例3-TSP问题

https://www.luogu.com.cn/problem/P1171

这里和上面的想法类似，注意此时走过是1，未走过是0

f中st代表状态，i代表目前在哪个村

f从1开始，表示0号村已经被走过，在f函数里，若st全置一，证明都走到了一遍，此时需要返回0号村，因此return到零号村的代价

dp状态返回同理

在走村时，遍历每一个村，若某位为0即未走过，就走，记录代价最小值

注意，洛谷的#9存在卡常，这里改成静态数组才过

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
int n;
int g[N][N];
int dp[1<<N][N];
int f(int st, int i)
{
  if (st==(1<<n)-1)
  {
    return g[i][0];
  }
  if (dp[st][i]!=-1)
  {
    return dp[st][i];
  }

  int ans = INT_MAX;
  for (int j = 0; j<n; j++)
  {
    if ((st&(1<<j))==0)
    {
      ans = min(ans, g[i][j]+f(st|(1<<j), j));
    }
  }
  dp[st][i] = ans;
  return ans;
}
void solve() {
  
  cin >> n;
  memset(dp, -1, sizeof(dp));
  
  for (int i = 0; i<n; i++)
  {
    for (int j = 0; j<n; j++)
    {
      cin >> g[i][j];
    }
  }
  cout << f(1,0);
  
}

例4-每个人戴不同帽子的方案数

注意选取什么元素当作状态

这个题里，人数最多10个，可以将人数作为状态使用

对每种出现的颜色，看他们能不能满足每个人（将他们编号），对应的是二进制位的不同位置

分为两种可能性：

  • i颜色的帽子不分配给任何人，直接跳到下一层
  • i颜色的帽子分配给0~n-1可能的每一个人

优化：可以不用枚举每一个人，而是从当前帽子中依次提取出能满足的人，即提取出二进制状态中最右侧的1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
int numberWays(vector<vector<int>>& hats) {
   int maxn = -1;
   for (auto lt: hats)
   {
    for (auto it: lt)
    {
        maxn = max(maxn, it);
    }
   } 

   vector<int> ph(maxn+1);
   int n = hats.size();
   for (int i = 0; i<n; i++)
   {
    for (auto it: hats[i])
    {
        ph[it]|=(1<<i);
    }
   }

   vector<vector<int>> dp(maxn+1, vector<int>((1<<n)+1, -1));

   return f(ph, n, maxn, 1, 0, dp);

}
int f(vector<int> &ph, int n, int m, int i, int st, vector<vector<int>>&dp)
{
    if (st==(1<<n)-1)  
    {
        return 1;
    }
    if (i==m+1) 
    {
        return 0;
    }
    if(dp[i][st]!=-1)
    {
        return dp[i][st];
    }
    int ans = f(ph,n, m, i+1, st, dp);
    int cur = ph[i];
    for (int j = 0; j<n; j++)
    {
        if ((cur&(1<<j))&&(st&(1<<j))==0)
        {
            ans = (ans+f(ph,n, m, i+1, st|(1<<j), dp))%mod;
        }

    } 
    dp[i][st] = ans;
    return ans;
}

例5-分配重复整数

用到的技巧：枚举st的所有子集状态

如：st目前的状态为1001100，它有多少子集状态

使用循环枚举：

1
for (int i = st, j>0; j = (j-1)&st) {...}

通过枚举quantity的每个子集，来记录每种情况所需要的重复数字个数

1
2
3
4
5
6
7
8
9
10
11
int m = quantity.size();
vector<int> sum((1<<m));
for (int i = 0; i<quantity.size(); i++)
{
    int v = quantity[i];
    int h = 1<<i;
    for (int j = 0; j<h; j++)
    {
        sum[h|j] = sum[j]+v; 
    }
}

我们需要看当前需要的数字数，在当前状态的某一个子集中是否满足，而不一定是该状态必须满足当前数字数，因为某个状态可以满足多个人需要的数字数，故需要枚举状态的子集

1
2
3
4
5
6
7
8
9
10
11
bool flag = 0;
    int c = cnt[i];
    for (int j = st; j>0; j = (j-1)&st)
    {
        if (sum[j]<=c&&f(cnt,sum, st^j, i+1, dp))
        {
            flag = 1;
            break;
        }
    }
if (!flag) flag = f(cnt, sum , st, i+1, dp);

Code：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
bool canDistribute(vector<int>& nums, vector<int>& quantity) {
   sort(nums.begin(), nums.end());
   int n = 1;
   for (int i = 1; i<nums.size(); i++) 
   {
    if (nums[i-1]!=nums[i]) n++;
   }
   vector<int> cnt(n,0);
   int c = 1;
   for (int i = 1, j = 0; i<nums.size(); i++)
   {
    if (nums[i-1]!=nums[i])
    {
        cnt[j++] = c;
        c = 1;
    }
    else
    {
        c++;
    }
   }

   cnt[n-1] = c;
   int m = quantity.size();
   vector<int> sum((1<<m));
   for (int i = 0; i<quantity.size(); i++)
   {
    int v = quantity[i];
    int h = 1<<i;
    for (int j = 0; j<h; j++)
    {
        sum[h|j] = sum[j]+v; 
    }
   }
   vector<vector<int>> dp(n, vector<int>((1<<m)));
   return f(cnt, sum, (1<<m)-1, 0, dp);
}
bool f(vector<int>& cnt, vector<int>& sum, int st, int i, vector<vector<int>>& dp)
{
    if (st==0) return true;
    if (cnt.size()==i) return false;
    if (dp[i][st]) return dp[i][st] == 1;   
    bool flag = 0;
    int c = cnt[i];
    for (int j = st; j>0; j = (j-1)&st)
    {
        if (sum[j]<=c&&f(cnt,sum, st^j, i+1, dp))
        {
            flag = 1;
            break;
        }
    }
    if (!flag) flag = f(cnt, sum , st, i+1, dp);
    dp[i][st] = flag?1:-1;
    return flag;
}

例6-小红的矩阵修改

https://www.nowcoder.com/practice/e556fd4852954529aec85940801200a1

三进制状态压缩

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
#include <bits/stdc++.h>
#define endl '\n'
using namespace std;
typedef long long ll;

void solve() {
  int n, m;
  cin >> n >> m;
  map<char, int> mp = {{'r',0},{'e',1},{'d',2}};
  vector<string> g(n);
  for (int i = 0; i<n; i++)
  {
    cin >> g[i];
  }

  ll mask = pow(3,n);


  vector<ll> ok;

  auto cost = [&](int fr, int to)
  {
    int c = 0;
    for (int i = 0; i<n; i++)
    {
      if(mp[g[i][fr]]!=to%3) c++;
      to/=3;
    }
    return c;
  };
  for (int i = 0; i<mask; i++)
  {
    bool flag =  true;
    int temp = i;
    int last = -1;
    for (int j = 0; j<n; j++)
    {
      int cur = temp%3;
      if (cur==last)
      {
        flag = false;
        break;
      }
      last = cur;
      temp/=3;
    }
    if (flag) ok.push_back(i);
  }

  vector<vector<ll>> dp(m+1, vector<ll>(mask, 0x3f3f3f3f));
  for (auto c: ok)
  {
    dp[0][c] = cost(0, c);
  }

  for (int i = 1; i<m; i++)
  {
    for (auto cur: ok)
    {
      int c = cost(i,cur);
      for (auto prv:ok)
      {
        bool flag = true;
        int tcur = cur, tprv = prv;
        for (int i = 0; i<n; i++)
        {
          if (tcur%3==tprv%3)
          {
            flag = false;
            break;
          }
          tcur/=3, tprv/=3;
        }
        if (flag)
        {
          dp[i][cur] = min(dp[i][cur], dp[i-1][prv]+c);
        }
      }
    }
  }

  ll ans = 0x3f3f3f3f;
  for (auto it: ok)
  {
    ans = min(ans, dp[m-1][it]);
  }

  cout << ans << endl;
  

}

int main()
{
  ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  int tomorin=1;
  //cin >> tomorin;
  while (tomorin--) solve();
  return 0;
}