“每天一遍，MLE再见。”
前言
对于一类题而言，如果用 $dp$ 来做的话，会有 $m$ 个状态，而作为我们来讲，我们不可能去开一个数组 $dp[2][2][2][2][2][2][2]…[2]$ 来记录，因为空间是动态的。所以我们考虑将这 $m$ 个状态压缩成一个 $m$ 位的二进制数。存储为一位，则空间复杂度与时间复杂度都是 $O(2^m)$ 的话，枚举 $[0,2^m-1]$ ，而对于这个二进制数，它的第 $k$ 位为 $1$ 则满足第 $k$ 个条件，判断语句为 if(i>>k&1) 即可。
这种题可实行的范围一般都不超过 $10 \sim 20$ ，所以很容易识别。
例题
最经典的状压题，我们用一个长度为 $n$ 的二进制数来存储，第 $k$ 位为 $0$ ，则表示第 $k$ 个点还没有到达；反之，则表示第 $k$ 个点已经到达。然后遍历即可，时间复杂度 $O(2^nn^2)$ 。
查看代码
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
| #include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<ctime>
#include<iomanip>
#include<queue>
#include<stack>
#include<map>
#include<vector>
#define gh() getchar()
#define re register
#define db double
typedef long long ll;
using namespace std;
const int MAXN=21;
const int MAXS=1<<21;
template<class T>
inline void read(T &x)
{
x=0;
char ch=gh(),t=0;
while(ch<'0'||ch>'9') t|=ch=='-',ch=gh();
while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+(ch^48),ch=gh();
if(t) x=-x;
}
int n;
int val[MAXN][MAXN],dp[MAXS][MAXN];
int main()
{
read(n);
for(int i=0;i<n;++i)
for(int j=0;j<n;++j)
read(val[i][j]);
memset(dp,0x3f,sizeof(dp));
dp[1][0]=0;
for(int i=0;i<(1<<n);++i)
for(int j=0;j<n;++j)
if(i>>j&1)
for(int k=0;k<n;++k)
if(i>>k&1)
dp[i][j]=min(dp[i][j],dp[i-(1<<j)][k]+val[k][j]);
printf("%d",dp[(1<<n)-1][n-1]);
return 0;
}
|
也是一道较为经典的状压dp题，考虑当前行与上一行的状态，满足：
- 没有相邻的 $1$
- $s_{line}\&s_{line-1}=0$
即可。
AC 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
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
| #include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<ctime>
#include<iomanip>
#include<queue>
#include<stack>
#include<map>
#include<vector>
#define gh() getchar()
#define re register
#define db double
typedef long long ll;
using namespace std;
const int MAXS=(1<<10)-1;
const int MAXN=10;
const int MAXK=101;
template<class T>
inline void read(T &x)
{
x=0;
char ch=gh(),t=0;
while(ch<'0'||ch>'9') t|=ch=='-',ch=gh();
while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+(ch^48),ch=gh();
if(t) x=-x;
}
template<class T>
inline bool checkMax(T &x,T &y)
{
return x<y?x=y,1:0;
}
template<class T>
inline bool checkMin(T &x,T &y)
{
return x>y?x=y,1:0;
}
int N,K,Total;
ll dp[MAXK][MAXN][MAXS],ok[MAXS],cnt[MAXS];
inline void init()
{
for(int s=0;s<(1<<N);++s)
{
int o=s,c=0;
while(o)
{
if(o&1) ++c;
o>>=1;
}
cnt[s]=c;
if(!(((s<<1)|(s>>1))&s)) ok[++Total]=s;
}
dp[0][0][0]=1;
}
int main()
{
read(N),read(K);
init();
for(int line=1;line<=N;++line)
for(int l=1;l<=Total;++l)
{
int sl=ok[l];
for(int r=1;r<=Total;++r)
{
int sr=ok[r];
if(!((sr|(sr<<1)|(sr>>1))&sl))
for(int k=0;k<=K;++k)
if(k-cnt[sl]>=0)
dp[k][line][sl]+=dp[k-cnt[sl]][line-1][sr];
}
}
ll ans=0;
for(int i=1;i<=Total;++i) ans+=dp[K][N][ok[i]];
printf("%lld",ans);
return 0;
}
|
这便是一道比较进阶的状压dp题了。因为对于一排而言，我们需要记录前两行的信息才能对该行的信息进行转移。所以需要维护前两行的状态，用 $dp[i][j][k]$ 表示第 $i$ 行的状态是 $j$ 并且 $i-1$ 行的状态是 $k$ 的答案总数。并对 $i-2$ 进行转移。
但是，这样的时间复杂度是 $2^{3m}n$ ，根本不够。所以，我们需要预处理出对于每一行而言的可行方案，直接在可行方案里计算即可。
然而，空间复杂度 $O(2^{2m}n)$ ，又超出了空间限制，所以我们可以像背包那样使用滚动数组。
查看代码
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
| #include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<ctime>
#include<iomanip>
#include<queue>
#include<stack>
#include<map>
#include<vector>
#define gh() getchar()
#define re register
#define db double
#define popcount(x) __builtin_popcount(x)
typedef long long ll;
using namespace std;
const int MAXN=101;
const int MAXM=11;
const int MAXS=1<<10|10;
const int INF=0x7f7f7f7f;
template<class T>
inline void read(T &x)
{
x=0;
char ch=gh(),t=0;
while(ch<'0'||ch>'9') t|=ch=='-',ch=gh();
while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+(ch^48),ch=gh();
if(t) x=-x;
}
int n,m,id[MAXS],sz;
int dp[2][MAXS][MAXS];
bool valid[MAXN][MAXM];
vector<int>V,okV[MAXS][MAXS];
char op[MAXM+5];
inline void init()
{
for(int s=0;s<(1<<m);++s)
{
bool flag=1;
for(int j=0;j<m-1&&flag;++j)
if(s>>j&1) flag=!(s>>(j+1)&1)&&!(s>>(j+2)&1);
if(flag) id[s]=V.size(),V.push_back(s);
}
sz=V.size();
for(int i=0;i<sz;++i)
for(int j=0;j<sz;++j)
{
if(V[i]&V[j]) continue;
for(int k=0;k<sz;++k)
if(!(V[i]&V[k])&&!(V[j]&V[k])) okV[i][j].push_back(k);
}
}
inline bool check(int op,int s)
{
for(int i=0;i<m;++i)
if((s>>i&1)&&!valid[op][i]) return 0;
return 1;
}
int main()
{
read(n),read(m);
init();
for(int i=1;i<=n;++i)
{
scanf("%s",op);
for(int j=0;j<m;++j) valid[i][j]=op[j]=='P';
}
for(int j=0;j<sz;++j)
for(int k=0;k<sz;++k)
dp[0][j][k]=-INF;
dp[0][0][0]=0;
for(int i=1;i<=n;++i)
{
for(int j=0;j<sz;++j)
for(int k=0;k<sz;++k)
dp[i&1][j][k]=-INF;
for(int j=0;j<sz;++j)
for(int k=0;k<sz;++k)
{
if(dp[(i-1)&1][j][k]==-INF) continue;
for(int nxt:okV[j][k])
if(check(i,V[nxt])) dp[i&1][nxt][j]=max(dp[i&1][nxt][j],dp[(i-1)&1][j][k]+popcount(V[nxt]));
}
}
int res=0;
for(int j=0;j<sz;++j)
for(int k=0;k<sz;++k)
res=max(res,dp[n&1][j][k]);
printf("%d",res);
return 0;
}
|
P3959 宝藏
求一个图的最小权生成树，这里的最小权关系到其生成高度。
定义状态为 $dp[i][s]$ 表示当前生成树的高度为 $i$ ，且点集状态为 $s $ 的情况。每一次转移 $s$ 的子集 $T$ 以及 $s$ 与 $T$ 相异的部分。
判断子集的方法： T=(T-1)&s 。
转移为：
$dp[i][s]=\min\{dp[i-1][T]+temp\times j\}$
AC 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
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
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
| #include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<ctime>
#include<iomanip>
#include<queue>
#include<stack>
#include<map>
#include<vector>
#define gh() getchar()
#define re register
typedef long long ll;
using namespace std;
const int MAXN=15;
const int MAXM=5e3+1;
const int MAXS=1<<MAXN;
const int INF=0x3f3f3f3f;
template<class T>
inline void read(T &x)
{
x=0;
char ch=gh(),t=0;
while(ch<'0'||ch>'9') t|=ch=='-',ch=gh();
while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+(ch^48),ch=gh();
if(t) x=-x;
}
template<class T,class ...T1>
inline void read(T &x,T1 &...x1)
{
read(x),read(x1...);
}
template<class T>
inline bool checkMax(T &x,T &y)
{
return x<y?x=y,1:0;
}
template<class T>
inline bool checkMin(T &x,T &y)
{
return x>y?x=y,1:0;
}
int N,M;
ll dp[MAXN][MAXS],w,ans=INF;
ll Path[MAXN][MAXN],Dist[MAXS];
int main()
{
read(N,M);
memset(Path,0x3f,sizeof(Path));
for(int i=1,u,v;i<=M;++i)
{
read(u,v,w);
--u,--v;
Path[u][v]=Path[v][u]=min(Path[u][v],w);
}
memset(dp,0x3f,sizeof(dp));
int S=(1<<N)-1;
for(int s=1;s<=S;++s)
for(int i=0;i<N;++i)
if((1<<i)|s==s)
{
Path[i][i]=0;
for(int k=0;k<N;++k)
if(Path[i][k]!=INF) Dist[s]|=(1<<k);
}
for(int i=0;i<N;++i) dp[0][1<<i]=0;
for(int s=2;s<=S;++s)
for(int T=s-1;T;T=(T-1)&s)
if((Dist[T]|s)==Dist[T])
{
ll res=0;
int sf=T^s;
for(int k=0;k<N;++k)
if((1<<k)&sf)
{
ll temp=INF;
for(int l=0;l<N;++l)
if((1<<l)&T) checkMin(temp,Path[l][k]);
res+=temp;
}
for(int j=1;j<N;++j)
if(dp[j-1][T]!=INF)
dp[j][s]=min(dp[j][s],dp[j-1][T]+res*j);
}
for(int i=0;i<N;++i) checkMin(ans,dp[i][S]);
printf("%lld",ans);
return 0;
}
|
总结
其实，状态压缩并不仅限于使用在dp内，很多地方都能用到。方便，但十分难调（机房某巨佬所言）。算是dp一环中比较难的一类了。（之后还会有四边形不等式和斜率优化）