动态规划是研究一大类问题(特别是最值问题)的一种思路。从大二刚开始 ICPC 竞赛的时候第一次遇到,到大三学运筹学系统的了解,再到后来一直成为解决问题的一种思考方式。可以说动态规划真的是万金油的方法。

计算机领域(或者说博弈论)中的动态规划,就如同数学中的数学归纳法,一样重要。

运用动态规划的能力,就好比武侠小说中的内功,是随着时间慢慢累积的。
进阶可看 zscoder 的博文

动态规划应用举例

  • 数列的递推关系
  • 背包问题
  • 图论中 Floyd 算法,Dijkstra 算法
  • 流水线问题,旅行商问题
  • 其它杂类问题

动态规划原理

动态规划(dynamic programming)于 1950s 被 Richard Bellman 发现。引用这里的话,动态规划本质就是:

  • 定义问题的状态(必须满足”无后效性”:这个就很玄学了)
  • 写出状态间的转移方程

从而递推(分治)的解决问题。

难点就在于定义问题的状态

很多时候一个变量的问题,我们需要强行加一个(甚至两个)变量来定义状态

然后给出状态转移方程,再做时间空间的优化。

常规动态规划的状态定义

  • 以该位置结尾的最优策略
  • 多设一个变量的最优策略

动态规划举例(长期更新)

codeforces1354F

有 $n$ 张牌,$i$ 号牌的数值是 $a_i$,当 $i$ 号牌放入桌上,之前在桌上的牌,每张数值增加 $b_i$,桌上的牌可以销毁(每张牌最多销毁一次),但是桌上牌的数量不能超过 $k$。 问使桌上牌数值总和最大的放法。其中数据满足

由于牌的编号于问题无关,所以不妨设 $b_i$ 单调递增。

状态定义:dp[i][j] 表示:场上前 $j$ 张牌数(编号都不超过 $i$ )的桌面牌总和最大值(其实还要减去后 $k-j$ 张牌的原始面值)。如果不减去就有后效性了!!!

状态转移:我们考虑第 $i$ 张牌,

  • 如果将它最终留在桌面上,那么它一定是最后一张放在桌面上的,因为 $b_i$ 单调递增。此时 $dp[i][j] = dp[i-1][j-1]+(j-1)b[i] + a[i]$
  • 如果它没留在桌面,那么它一定会在后来第 $k$ 张牌加过 buff,$dp[i][j] = dp[i-1][j] + (k-1)b[i]$

所以

我们可以用 isin[i][j] 来标记桌上第 $j$ 张牌是否是 $i$ 号牌。

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
#include<bits/stdc++.h>
using namespace std;
const int N = 102;
int dp[N][N];
bool isin[N][N],chose[N];
using node = tuple<int,int,int>;
node q[N];
void getans(int n,int k){
for(int i=1;i<=n;++i){
dp[i][0] = dp[i-1][0]+(k-1)*get<2>(q[i]);
for(int j = 1;j<i && j<=k;++j){
int x = dp[i-1][j]+(k-1)*get<2>(q[i]);
int y = dp[i-1][j-1]+(j-1)*get<2>(q[i])+get<1>(q[i]);
if(x>y){
dp[i][j] = x;
isin[i][j] = false;
}else{
dp[i][j] = y;
isin[i][j] = true;
}
}
if(i<=k){
dp[i][i] = dp[i-1][i-1]+(i-1)*get<2>(q[i])+get<1>(q[i]);
isin[i][i] = true;
}
}
for(int i=n,j=k;i;--i){
if(isin[i][j]){
chose[i]=true;
--j;
}else{
chose[i]=false;
}
}
}

int main(){
//freopen("in","r",stdin);
std::ios::sync_with_stdio(false);std::cin.tie(nullptr);
int cas,n,k,a,b;
cin>>cas;
while(cas--){
cin>>n>>k;
for(int i=1;i<=n;++i){
cin>>a>>b;
q[i] = {i,a,b};

}
sort(q+1,q+n+1,[](const node & x, const node & y){
return get<2>(x)<get<2>(y);
});
cout<<(2*n-k)<<endl;
getans(n,k);
int last = 0;
for(int i=1;i<=n;++i){
if(chose[i]){
if(++last == k){
last = i;
break;
}
cout<<get<0>(q[i])<<" ";
}
}
for(int i=1;i<=n;++i){
if(!chose[i]) cout<<get<0>(q[i])<<" "<<-get<0>(q[i])<<" ";
}
cout<<get<0>(q[last])<<endl;
}
return 0;
}

hdu 5691

这题大意:给你一些数,数值固定,部分数的位置随意调节,问你如何调解使得下式取值最大

这确实是经典的状态转移问题:

设 $i$ 的 2 进制表示是 $0 \cdots 0 i_1 0 \cdots 0 i_x 0\cdots 0$ 有 $x$ 位。
dp[i][j] 表示前 $x$ 个空 分别填了 $a[i_1],a[i_2],\cdots,a[i_x]$ 的一个排列 且 $i_x = j$ 使目标最大的最大值。
那么,自然地有 dp[i|(1<<k)][k] = max(dp[i][j]+a[j]*a[k])

详细转移见代码:

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
#include <cstdio>
template<typename T>
void upmax(T &a,T b){ if (a<b) a=b;}
const int INF = 0x3f3f3f3f;
const int N = 16;
int a[N],p[N];
int dp[1<<N][N];
int main(){
int T, Case = 0;
scanf("%d",&T);
while(T--){
printf("Case #%d:\n",++Case);
int n, x;
scanf("%d",&n);
for(int i=0;i<n;++i) p[i] = -1;
for(int i=0;i<n;++i){
scanf("%d%d",a+i, &x);
if(x != -1) p[x] = i;
}
for(int i=0;i<(1<<n);++i){
for(int j=0;j<n;++j){
dp[i][j] = -INF;
}
}
if(p[0]!=-1) dp[1<<p[0]][p[0]] = 0;
else for(int i=0;i<n;++i) dp[1<<i][i] = 0;
for(int i=1;i<(1<<n);++i){
for(int j=0;j<n;++j){
if(!(i&(1<<j))) continue;
for(int k=0;k<n;++k){
if(i&(1<<k)) continue;
int x = __builtin_popcount(i);
if(p[x] == -1 || p[x] == k){
upmax(dp[i|(1<<k)][k], dp[i][j]+a[j]*a[k]);
}
}
}
}
int res = -INF;
for(int i=0;i<n;++i) upmax(res, dp[(1<<n)-1][i]);
printf("%d\n",res);
}
return 0;
}

Codeforces 1312E

我们用 ans[i][j] 表示前 i 个数中以 j 结尾的最短数列长度,并用 b[i][j] 保存导致它以 j 结尾的前缀首项的位置。那么状态转移就显然,可从代码中读取。

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
#include<bits/stdc++.h>
using namespace std;
using LL = long long;
const int N = 1022;
const int inf = 0x3f3f3f3f;
int ans[502][N],b[502][N];

int main(){
//freopen("in","r",stdin);
std::ios::sync_with_stdio(false);std::cin.tie(nullptr);
int n,x;
while(cin>>n){
memset(ans,inf,sizeof(ans));
cin>>x;
ans[0][x] = 1;
b[0][x]=0;
for(int i=1;i<n;++i){
cin>>x;
for(int j=1;j<N;++j){
if(ans[i-1][j]!=inf){
ans[i][x] = min(ans[i][x],ans[i-1][j]+1);
}
b[i][x]=i;
}
int s = i-1;
while(s>=0&&ans[s][x]!=inf){
ans[i][x+1] = ans[s][x];
b[i][x+1] = b[s][x];
s = b[s][x]-1;
++x;
}
}
int r = inf;
for(int i=1;i<N;++i){
r = min(r,ans[n-1][i]);
}
cout<<r<<endl;
}
return 0;
}

洛谷 P1005 矩阵取数游戏

每一行单独考虑,然后因为数据范围,所以用 Python 交题

按照规模做 dp,最近做的很少,记录一哈 2020/7/4

1
2
3
4
5
6
7
8
9
10
11
12
13
14
def f(a):
b = a.copy()
for i in range(1,len(a)):
c = []
for j in range(0,len(b)-1):
c.append(max(2*b[j]+a[i+j],2*b[j+1]+a[j]))
b=c
return 2*b[0]

n = int(input().split()[0])
r=0
for i in range(n):
r += f([int(_) for _ in input().split()])
print(r)

洛谷 T135246 「SWTR-05」Grid

dp[i][j] :第 i 行,以第 j 个数结尾的最小和, s[i][j] :第 i 行,前 j 个数之和

rr[i][j] :到达 i,j 位置经过的数字和。

r[i][j] :首次到达 i,j 位置经过格子的数字和(不包括 i,j 的值)初值为 rr[i+1][j]

dp[i][j]s[i][j] 的状态转移是显然的,rr[i][j]r[i][j] 状态转移:

由于 r[i][j] 转移式的对称性,我们考虑记录 s[i][j] + r[i][j] 的最小值,(直接优化了一个 $O(m)$),这也是此题的经典之处。最后 rr 数组可被优化掉。当然也可以对 r 进行空间优化,但是没必要

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
#include<bits/stdc++.h>
using namespace std;
using LL = long long;

int main(){
//freopen("in","r",stdin);
std::ios::sync_with_stdio(false);std::cin.tie(nullptr);
int n,m;
cin>>n>>m;
LL a[n][m],dp[n][m],s[n][m],r[n+1][m];
for(int i=0;i<n;++i){
int cur = 0;
for(int j=0;j<m;++j){
cin>>a[i][j];
if(j==0) s[i][j] = a[i][j];
else s[i][j] = s[i][j-1]+a[i][j];
cur += a[i][j];
dp[i][j] = cur;
cur = min(cur,0);
}
}
for(int i=n-1;i>=0;--i){
LL mi = 1e9+2;
for(int j=m-1;j>=0;--j){
r[i][j] = (i==n-1?0:r[i+1][j]);
if(r[i][j]<mi-s[i][j]){
mi = r[i][j]+s[i][j];
}else{
r[i][j] = mi-s[i][j];
}
}
for(int j=0;j<m;++j){
r[i][j] += dp[i][j];
}
}
LL ret = r[0][0];
for(int j=1;j<m;++j){
ret = min(ret,r[0][j]);
}
cout<<ret<<endl;
return 0;
}

下面上题的 空间优化版本(优雅的不行,需要考虑从上向下走)

rr[j] 表示上一行的答案, r[j] 表示当前行的答案。那么 r[j] 的初始值应该为 rr[j]+dp[j],状态转移

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
#include<bits/stdc++.h>
using namespace std;
using LL = long long;

int main(){
//freopen("in","r",stdin);
std::ios::sync_with_stdio(false);std::cin.tie(nullptr);
int n,m;
cin>>n>>m;
LL a[m],s[m],dp[m],r[m],rr[m]={};
for(int i=0;i<n;++i){
LL cur = 0;
for(int j=0;j<m;++j){
cin>>a[j];
cur += a[j];
dp[j] = cur;
cur = min(cur,0LL);
s[j] = a[j]+(j==0?0:s[j-1]);
}
cur = rr[0]+dp[0]-s[0];
for(int j=0;j<m;++j){
r[j] = min(rr[j]+dp[j],cur+s[j]);
cur = min(cur,r[j]-s[j]);
}
for(int j=0;j<m;++j) rr[j] = r[j];
}
cout<<*min_element(rr,rr+m)<<endl;
return 0;
}

T134867 [YsOI2020]归零

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
#include<bits/stdc++.h>
using namespace std;
using LL = long long;
const LL M = 998244353;
const int N = 132;
LL f[N],invf[N];
LL pow_mod(LL x,LL n){
LL r = 1;
while(n){
if(n&1) r=r*x%M;
n>>=1; x=x*x%M;
}
return r;
}
void init(){
f[0]=1;
for(int i=1;i<N;++i) f[i]=f[i-1]*i%M;
invf[N-1] = pow_mod(f[N-1],M-2);
for(int i=N-2;i>=0;--i) invf[i] = invf[i+1]*(i+1)%M;
}
LL C(int n,int k){
if(k>n) return 0;
return f[n]*invf[n-k]%M*invf[k]%M;
}
int main(){
//freopen("in","r",stdin);
std::ios::sync_with_stdio(false);std::cin.tie(nullptr);
init();
string ss;
cin>>ss;
vector<int> s={0};
for(auto &c:ss) s.emplace_back(c-'0');
auto plusOne = [&](int l,int r){
int id = r-1;
while(s[id]==9) --id;
++s[id];
for(int i=id+1;i<r;++i) s[i] = 0;
};
auto minusOne = [&](int l,int r){
int id = r-1;
while(s[id]==0) --id;
--s[id];
for(int i=id+1;i<r;++i) s[i] = 9;
};
function<map<int,LL>(int,int)> f = [&](int l,int r) -> map<int,LL>{
if(all_of(s.begin()+l,s.begin()+r,[](int x){ return x == 0;})){
return map<int,LL>{{0,1}};
}
map<int,LL> ret;
for(int i=l;i<r;++i){
if(s[i]){
int x = s[i];
s[i]=0;
if(x>4) plusOne(l,i);
for(auto &ia:f(l,i)){
for(auto &ib:f(i,r)){
int t1 = 1+ia.first+ib.first;
LL t2 = ia.second*ib.second%M*C(ia.first+ib.first,ia.first)%M;
if(ret.find(t1)==ret.end()){
ret[t1] = t2;
}else ret[t1] = (ret[t1]+t2)%M;
}
}
if(x>4) minusOne(l,i);
s[i]=x;
}
}
return ret;
};
LL res = 0;
for(auto &x:f(0,s.size())){
//cout<<x.first<<" "<<x.second<<endl;
res+=x.second;
}
cout<<res%M<<endl;
return 0;
}

状态压缩 DP(mask dp)

给定 $2n$ 个非负整数,求两两配对的最大公约数的和的最大值

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
#include <bits/stdc++.h>
#define watch(x) std::cout << (#x) << " is " << (x) << std::endl
#define print(x) std::cout << (x) << std::endl
#define println std::cout << std::endl
using LL = long long;

int main() {
//freopen("in","r",stdin);
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);

// input n and 2n non-negetive integers(less than 1e9)
int n;
std::cin >> n;
n *= 2;
std::vector<int> a(n);
for (auto &x : a) std::cin >> x;
// initial all gcd which will be used for effectiveness
std::vector<std::vector<int>> gcd(n, std::vector<int>(n));
for (int i = 1; i < n; ++i) {
for (int j = 0; j < i; ++j) {
gcd[i][j] = std::__gcd(a[i], a[j]);
}
}

auto cmax = [](LL &a, LL b) {
if (a < b) a = b;
};
// total complex O(2^n * n^3) and we can remove the "if" part of following code
std::vector<LL> mask(1 << n);
for (int step = 0; step < n; ++step) { // every step choose two integers
for (int msk = 0; msk < (1 << n); ++msk) if (__builtin_popcount(msk) == 2 * step) {
for (int i = 1; i < n; ++i) if (!(msk & (1 << i))) {
for (int j = 0; j < i; ++j) if (!(msk & (1 << j))) {
cmax(mask[msk|(1 << i)|(1 << j)], mask[msk] + gcd[i][j]);
}
}
}
}

print(mask.back());

return 0;
}

本问题可以在多项式时间用一般图匹配 解决。

旅行商问题

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
#include <bits/stdc++.h>
#define watch(x) std::cout << (#x) << " is " << (x) << std::endl
#define print(x) std::cout << (x) << std::endl
#define println std::cout << std::endl
using LL = long long;

int main() {
//freopen("in","r",stdin);
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
int n;
std::cin >> n;
std::vector<std::tuple<int, int, int>> a(n);
for (auto &[x, y, z] : a) std::cin >> x >> y >> z;
auto dist = [&](int i, int j) {
auto [aix, aiy, aiz] = a[i];
auto [ajx, ajy, ajz] = a[j];
return abs(aix - ajx) + abs(aiy - ajy) + std::max(0, ajz - aiz);
};
std::vector<std::vector<int>> d(n, std::vector<int>(n));
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
d[i][j] = dist(i, j);
}
}
auto cmin = [](int &a, int b) {
if (a > b) a = b;
};
std::vector<std::vector<int>> mask(1 << n, std::vector<int>(n, 1e8));
mask[1][0] = 0;
for (int step = 1; step < n; ++step) {
for (int msk = 1; msk < (1 << n); msk += 2) if (__builtin_popcount(msk) == step) {
for (int i = 0; i < n; ++i) if (msk & (1 << i)) {
for (int j = 1; j < n; ++j) if (!(msk & (1 << j))) {
cmin(mask[msk|(1 << j)][j], mask[msk][i] + d[i][j]);
}
}
}
}
int r = 1e8;
for (int i = 1; i < n; ++i) r = std::min(r, mask[(1 << n) - 1][i] + d[i][0]);
print(r);
return 0;
}

453B:状态压缩 DP

给定数列 $a$,求满足元素两两互素的数列 $b$ 使得 $\sum |a_i - b_i|$ 最小

注意到 $b_i < 2 a_i$,因为否则取 $b_i = 1$ 即可。

由于 $60$ 内的素数个数为 17, 因此可以状态压缩 DP。设 dp[i][j] 表示使得 $\sum_{k = 1} ^ i |a_k - b_k|$ 最小,且$b_1 \cdots b_i$ 中所有出现的素因子的状态为 $j$。因此状态转移就是 dp[i][j | factor[k]] = min(dp[i - 1][j] + |a_i - k|),其中 factor[k] 与 $j$ 没有交集。

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
#include <bits/stdc++.h>
#define watch(x) std::cout << (#x) << " is " << (x) << std::endl
#define print(x) std::cout << (x) << std::endl
#define println std::cout << std::endl
using LL = long long;

int main() {
//freopen("in","r",stdin);
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
int n;
std::cin >> n;
std::vector<int> a(n);
for (auto &x : a) std::cin >> x;
int ma = *std::max_element(a.begin(), a.end()) * 2;
std::vector<int> p;
for (int i = 2; i < ma; ++i) {
bool flag = true;
for (int j = 2; j * j <= i; ++j) if (i % j == 0) {
flag = false;
break;
}
if (flag) p.emplace_back(i);
}
std::vector<int> factor(ma);
for (int i = 2; i < ma; ++i) {
for (int j = 0; j < p.size(); ++j) if (i % p[j] == 0) {
factor[i] |= (1 << j);
}
}
std::vector<std::vector<int>> ans(n + 1, std::vector<int>(1 << p.size(), 1e9));
ans[0][0] = 0;
for (int i = 1; i <= n; ++i) {
for (int j = 1; j < 2 * a[i - 1]; ++j) {
for (int k = 0; k < (1 << p.size()); ++k) if ((k & factor[j]) == 0) {
ans[i][k | factor[j]] = std::min(ans[i][k | factor[j]], ans[i - 1][k] + abs(a[i - 1] - j));
}
}
}
std::vector<int> r(n);
int now = std::min_element(ans[n].begin(), ans[n].end()) - ans[n].begin();
for (int i = n - 1; i >= 0; --i) {
for (int j = 1; j < 2 * a[i]; ++j) if ((now | factor[j]) == now) {
if (ans[i][now ^ factor[j]] + abs(a[i] - j) == ans[i + 1][now]) {
r[i] = j;
now ^= factor[j];
break;
}
}
}
for (auto x : r) std::cout << x << " ";
println;
return 0;
}

662C:状态压缩 DP + FWT 模板

给定 $n \times m$ 的 0-1 方阵,可以取反一些行和列使得最后 0 的数列最小。

首先注意到 $n < 20$,我们可以把每一列看作一个状态 i ,并且结果跟列的顺序无关。我们可以记录下初始情况每种状态数 C[i] 量。
并且每一种状态 i 对答案的贡献显然就是它的 0, 1 个数的最小值记作 g[i]
对于每一个行取反 S, 其实就是将一个状态 i 变成 状态 i ^ S
所以每一种行取反 S,最终的答案 $\displaystyle F(S) = \sum_{i} C[i] \cdot g[i \wedge S] = \sum_{i \wedge j = S} C[i] \cdot g[j]$

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
101
102
103
104
105
106
107
108
109
110
111
112
113
114
#include <bits/stdc++.h>
#define watch(x) std::cout << (#x) << " is " << (x) << std::endl
#define print(x) std::cout << (x) << std::endl
#define println std::cout << std::endl
using LL = long long;

#include <cstdio>
#include <algorithm>
#include <vector>

const int P = 998244353;

void add(int &x, int y) {
(x += y) >= P && (x -= P);
}
void sub(int &x, int y) {
(x -= y) < 0 && (x += P);
}
struct FWT {
int extend(int n) {
int N = 1;
for (; N < n; N <<= 1);
return N;
}
void FWTor(std::vector<int> &a, bool rev) {
int n = a.size();
for (int l = 2, m = 1; l <= n; l <<= 1, m <<= 1) {
for (int j = 0; j < n; j += l) for (int i = 0; i < m; i++) {
if (!rev) add(a[i + j + m], a[i + j]);
else sub(a[i + j + m], a[i + j]);
}
}
}
void FWTand(std::vector<int> &a, bool rev) {
int n = a.size();
for (int l = 2, m = 1; l <= n; l <<= 1, m <<= 1) {
for (int j = 0; j < n; j += l) for (int i = 0; i < m; i++) {
if (!rev) add(a[i + j], a[i + j + m]);
else sub(a[i + j], a[i + j + m]);
}
}
}
void FWTxor(std::vector<int> &a, bool rev) {
int n = a.size(), inv2 = (P + 1) >> 1;
for (int l = 2, m = 1; l <= n; l <<= 1, m <<= 1) {
for (int j = 0; j < n; j += l) for (int i = 0; i < m; i++) {
int x = a[i + j], y = a[i + j + m];
if (!rev) {
a[i + j] = (x + y) % P;
a[i + j + m] = (x - y + P) % P;
} else {
a[i + j] = 1LL * (x + y) * inv2 % P;
a[i + j + m] = 1LL * (x - y + P) * inv2 % P;
}
}
}
}
std::vector<int> Or(std::vector<int> a1, std::vector<int> a2) {
int n = std::max(a1.size(), a2.size()), N = extend(n);
a1.resize(N), FWTor(a1, false);
a2.resize(N), FWTor(a2, false);
std::vector<int> A(N);
for (int i = 0; i < N; i++) A[i] = 1LL * a1[i] * a2[i] % P;
FWTor(A, true);
return A;
}
std::vector<int> And(std::vector<int> a1, std::vector<int> a2) {
int n = std::max(a1.size(), a2.size()), N = extend(n);
a1.resize(N), FWTand(a1, false);
a2.resize(N), FWTand(a2, false);
std::vector<int> A(N);
for (int i = 0; i < N; i++) A[i] = 1LL * a1[i] * a2[i] % P;
FWTand(A, true);
return A;
}
std::vector<int> Xor(std::vector<int> a1, std::vector<int> a2) {
int n = std::max(a1.size(), a2.size()), N = extend(n);
a1.resize(N), FWTxor(a1, false);
a2.resize(N), FWTxor(a2, false);
std::vector<int> A(N);
for (int i = 0; i < N; i++) A[i] = 1LL * a1[i] * a2[i] % P;
FWTxor(A, true);
return A;
}
} fwt;

int main() {
//freopen("in","r",stdin);
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
int n, m;
std::cin >> n >> m;
std::vector<std::string> a(n);
for (auto &x : a) std::cin >> x;
std::vector<int> c(1 << n), g(1 << n);
for (int i = 0; i < m; ++i) {
int r = 0;
for (int j = 0; j < n; ++j) {
r |= (a[j][i] - '0') << j;
}
++c[r];
}
for (int i = 0; i < n; ++i) {
for (int j = 0; j < (1 << n); ++j) {
if (j & (1 << i)) ++g[j];
}
}
for (int i = 0; i < (1 << n); ++i) {
g[i] = std::min(g[i], n - g[i]);
}
auto f = fwt.Xor(c, g);
print(*std::min_element(f.begin(), f.end()));
return 0;
}

树形 DP

树形 DP 本质上就是,树结构可以给出各种不同的偏序关系,针对不同的问题,给出偏序关系,再来 DP