啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊我dp菜死了快来补一下。基本没讲解，来就放代码，偶尔写两句，也是在瞎扯。
简介
动态规划(dynamic programming)是运筹学的一个分支，是求解决策过程(decision process)最优化的数学方法。20世纪50年代初美国数学家R.E.Bellman等人在研究多阶段决策过程(multistep decision process)的优化问题时，提出了著名的最优化原理(principle of optimality)，把多阶段过程转化为一系列单阶段问题，利用各阶段之间的关系，逐个求解，创立了解决这类过程优化问题的新方法——动态规划。
线性DP
LIS
$O(nlong)$的方法用二分优化。
#include<bits/stdc++.h> using namespace std; int n,a[100005],f[100005],cnt; int main() { ios::sync_with_stdio(false); cin>>n; for(int i=1;i<=n;i++)cin>>a[i]; for(int i=1;i<=n;i++) { if(f[cnt]<a[i])f[++cnt]=a[i]; else { int mid=upper_bound(f+1,f+1+cnt,a[i])-f; f[mid]=a[i]; } } cout<<cnt<<" "; return 0; }
LCS
困死我了。
#include<bits/stdc++.h> using namespace std; int f[5005][5005],n; char a[5005],b[5005]; int main() { ios::sync_with_stdio(false); // cin>>n; scanf("%s",a); scanf("%s",b); int la=strlen(a),lb=strlen(b); for(int i=1;i<=la;i++) for(int j=1;j<=lb;j++) { if(a[i-1]==b[j-1])f[i][j]=max(f[i-1][j-1]+1,f[i][j]); f[i][j]=max(f[i][j],max(f[i-1][j],f[i][j-1])); } cout<<f[la][lb]<<" "; return 0; }
LCIS
我真的好困。。
#include<bits/stdc++.h> using namespace std; int n,a[5005],b[5005],f[5005][5005]; int main() { ios::sync_with_stdio(false); cin>>n; for(int i=1;i<=n;i++)cin>>a[i]; for(int j=1;j<=n;j++)cin>>b[j]; for(int i=1;i<=n;i++) { int val=0; if(b[0]<a[i])val=f[i-1][0]; for(int j=1;j<=n;j++) { if(a[i]==b[j])f[i][j]=val+1; else f[i][j]=f[i-1][j]; if(b[j]<a[i])val=max(val,f[i-1][j]); } } int maxn=0; for(int i=1;i<=n;i++)maxn=max(maxn,f[n][i]); cout<<maxn<<" "; return 0; }
背包问题
背包是一类经典dp。
01背包
有N件物品和一个容量为V的背包。第i件物品的费用是c[i]，价值是w[i]。求解将哪些物品装入背包可使价值总和最大。
关于初始化:
如果要求了把背包放满，那么初始化f[0]=0,f[1~n]=-INF。
如果没有要求放满，初始化为0。
所有的背包问题基本都这样初始化。
我们把j从m循环到w[i]:
1.寻找放了w[i]后剩余空间的最大值。
2.从大到小循环，保证当前状态的上一个状态不会出现已有当前物品的情况。
#include<cstdio> #include<algorithm> using namespace std; int n,m,w[205],c[205],f[205]; int main() { scanf("%d%d",&m,&n); for(int i=1;i<=n;i++) scanf("%d%d",&w[i],&c[i]); for(int i=1;i<=n;i++) for(int j=m;j>=w[i];j--) f[j]=max(f[j],f[j-w[i]]+c[i]); printf("%d ",f[m]); return 0; }
完全背包
有N种物品和一个容量为V的背包，每种物品都有无限件可用。第i种物品的费用是c[i]，价值是w[i]。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大。
和0~1背包的唯一区别就是有可能一个物品放多种。
反正是同样的背包，你换一换第二维循环顺序不就行了吗？这样其实就是从绝不可能重复到可能重复，刚好满足完全背包的要求，理解清了0/1的循环顺序，这个也就没问题了。
#include<cstdio> #include<algorithm> using namespace std; int n,m,w[205],c[205],f[205]; int main() { scanf("%d%d",&m,&n); for(int i=1;i<=n;i++) scanf("%d%d",&w[i],&c[i]); for(int i=1;i<=n;i++) for(int j=w[i];j<=m;j++) f[j]=max(f[j],f[j-w[i]]+c[i]); printf("max=%d ",f[m]); return 0; }
多重背包
有N种物品和一个容量为V的背包。第i种物品最多有n[i]件可用，每件费用是c[i]，价值是w[i]。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大。
这个题可以用二进制拆分思想来做，把每一个n[i]的系数化为1,2,4,...,2^(k-1),n[i]-2^k+1。
假如有一个n[i]=13，那么13=(2^0)+(2^1)+(2^2)+13-(2^3)+1，k在此处为3。
这样可以保证0~n[i]区间的每一个整数都可以用这些系数相加得到。
所以该问题能转化为0/1背包。
注意处理n-(2^k)+1。
多重背包复杂度O(vΣNi=1logn[i])
#include<cstdio> #include<cstring> #include<algorithm> using namespace std; int n,type,m,v,wt,num; int T; struct node { int w=0,c=0; }; int f[1005]; int main() { scanf("%d",&T); while(T--) { n=0; node a[1005]; scanf("%d%d",&m,&type); while(type--) { scanf("%d%d%d",&v,&wt,&num); int p=1; while(num-p>0) { num-=p; a[++n].w=v*p; a[n].c=wt*p; p<<=1; } a[++n].w=num*v; a[n].c=wt*num; //注意要处理n[i]-(2^k)+1这个情况 } memset(f,0,sizeof(f)); for(int i=1;i<=n;i++) for(int j=m;j>=a[i].w;j--) f[j]=max(f[j],f[j-a[i].w]+a[i].c); printf("%d ",f[m]); } return 0; }
单调队列优化多重背包以后再写。
混合背包
就是把01，完全，多重这三种背包混合在一起。
思路:
for i=1..N
if 第i件物品是01背包
ZeroOnePack(c[i],w[i])
else if 第i件物品是完全背包
CompletePack(c[i],w[i])
else if 第i件物品是多重背包
MultiplePack(c[i],w[i],n[i])
#include<cstdio> #include<algorithm> using namespace std; int n,m,f[205],cnt; struct node { int w,c,flag; }a[205]; int main() { scanf("%d%d",&m,&n); while(n--) { int ww,cc,p; scanf("%d%d%d",&ww,&cc,&p); if(p==0){a[++cnt].w=ww,a[cnt].c=cc;continue;} else { int mul=1; while(p-mul>0) { p-=mul; a[++cnt].c=mul*cc; a[cnt].w=mul*ww; a[cnt].flag=1; mul<<=1; } a[++cnt].c=p*cc; a[cnt].w=p*ww; a[cnt].flag=1; } } for(int i=1;i<=cnt;i++) { if(a[i].flag) for(int j=m;j>=a[i].w;j--) f[j]=max(f[j],f[j-a[i].w]+a[i].c); else for(int j=a[i].w;j<=m;j++) f[j]=max(f[j],f[j-a[i].w]+a[i].c); } printf("%d ",f[m]); return 0; }
看到这里累了吗？我也好累，不过挺开心的。qwq
二维费用背包
就是说有两种背包容量，两种体积（咋好理解咋来ber），我这里给出01二维背包，正常人都会推广到二维费用完全、多重、混合。
#include<cstdio> #include<algorithm> using namespace std; int n,M,T,m[205],t[205],f[205][205]; int main() { scanf("%d%d%d",&n,&M,&T); for(int i=1;i<=n;i++) scanf("%d%d",&m[i],&t[i]); for(int i=1;i<=n;i++) for(int j=M;j>=m[i];j--) for(int k=T;k>=t[i];k--) f[j][k]=max(f[j][k],f[j-m[i]][k-t[i]]+1); printf("%d ",f[M][T]); return 0; }
分组背包
有N件物品和一个容量为V的背包。第i件物品的费用是c[i]，价值是w[i]。这些物品被划分为若干组，每组中的物品互相冲突，最多选一件。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大。
其实就是01背包上面加了一维，假设划分为m组，每一组只能选一个，那么在01基础上套一维就行，不过要注意每一维的顺序，这很重要。如果顺序无法独立写正确，那么就代表没有理解分组背包的思想。
最外层的i好理解。
j也很好理解，把j放在cnt[i]的外面，其原因是每一个j只能由1~cnt[i]中的一个物品转移而来，最终会保留j在1~cnt[i]中的最优解，也就是说针对第i组，每一个j我们只选出一个k作为最优解，然后去循环下一组。
#include<cstdio> #include<algorithm> using namespace std; int n,m,cnt[205],T,f[205]; struct node { int w,c; }a[15][35]; int main() { scanf("%d%d%d",&m,&n,&T); while(n--) { int ww,cc,p; scanf("%d%d%d",&ww,&cc,&p); a[p][++cnt[p]].w=ww; a[p][cnt[p]].c=cc; } for(int i=1;i<=T;i++) for(int j=m;j>=0;j--) for(int k=1;k<=cnt[i];k++) if(j-a[i][k].w>=0)f[j]=max(f[j],f[j-a[i][k].w]+a[i][k].c); printf("%d ",f[m]); return 0; }
背包问题的变形
在背包问题中，很多时候不只是要求最大价值，还有很多有趣的变形。
输出方案
平时我们基本不会求方案数，但实际上方案在我们求解的过程中就已经体现了出来，以01背包举例。
$f[i][v]=max{f[i-1][v],f[i-1][v-c[i]]+w[i]}$，那么我们可以设置一个数组$g[i][v]$，若$f[i][v]=f[i-1][v]$，那么$g[i][v]=0$，否则$g[i][v]=1$，也就是表示第$i$项选或不选，最后输出。
伪代码如下
i=N v=V while(i>0) if(g[i][v]==0) print "未选第i项物品" else if(g[i][v]==1) print "选了第i项物品" v=v-c[i]
输出字典序最小的最优方案
这个我也不怎么理解，我也懒得在背包上面耗费过多时间。
简单来说，逆序排序物品，再正常跑方案数即可。
注意一个特殊情况，如果$f[i][v]=f[i-1][v]$和$f[i][v]=f[i-1][v-w[i]]+c[i]$是同时成立的，我们把后者的贡献计入答案而不是前者。
方案总数
在我们已经得到了诸多条件的时候，我们不仅可以求出最大贡献，还可以求出把背包装满或者装至某个容量的方案数，只需要把$max$改成$sum$。
$f[i][v]=f[i-1][v]+f[i-1][v-w[i]]$
最优方案总数
不同于方案总数，我们加上了“最优”的限制条件，很明显我们要考虑价值，那么分类讨论。
如果$f[i][j]=f[i-1][j]$，那么$g[i][j]=g[i-1][j]$
如果在当前状态下$f[i][j]=f[i-1][j-w[i]]+c[i]$，那么$g[i][j]=g[i-1][j-w[i]]$。
如果在当前状态下$f[i][j]=f[i-1][j]=f[i-1][j-w[i]]+c[i]$，那么$g[i][j]=g[i-1][j]+g[i-1][j-w[i]]$。
求第k优解
在最优解的基础上多了一个$K$的复杂度，只需要把原来的解排序（最优解到最不优解）然后统计，最后求出来就行了。
初始化？可以不写。
#include<bits/stdc++.h> using namespace std; int T,N,V,K,f[1005][35],c[1005],v[1005],tmp1[1005],tmp2[1005]; int main() { scanf("%d",&T); while(T--) { memset(f,0,sizeof f); memset(tmp1,0,sizeof tmp1); memset(tmp2,0,sizeof tmp2); scanf("%d%d%d",&N,&V,&K); for(int i=1;i<=N;i++)scanf("%d",&c[i]); for(int i=1;i<=N;i++)scanf("%d",&v[i]); for(int i=1;i<=N;i++) for(int j=V;j>=v[i];j--) { for(int k=1;k<=K;k++) tmp1[k]=f[j][k],tmp2[k]=f[j-v[i]][k]+c[i]; tmp1[K+1]=tmp2[K+1]=-1; int cnt=1,x=1,y=1; while(cnt!=K+1&&(tmp1[x]!=-1||tmp2[x]!=-1)) { if(tmp1[x]>tmp2[y])f[j][cnt]=tmp1[x],x++; else f[j][cnt]=tmp2[y],y++; if(f[j][cnt]!=f[j][cnt-1])cnt++; } } printf("%d ",f[V][K]); } return 0; }
区间DP
例1 [NOI1995]石子合并
首先断环成链，考虑设计状态，$f[l][r]$表示把第$l$到第$r$堆石子合并直到$l$,$r$相邻的分数，那么我们可以设计一个中间决策$k$，表示$l$~$r$可以由$l$~$k$和$k+1$~$r$转移过来，这就有点像$Floyd$算法的寻找中间点，有一点分治的意味在里面，但是我们合并$l$~$r$时，不仅仅有中间转移的分数贡献，而且还有$sum_{i=l}^{r}a_i$的分数贡献，因为每一次的合并算上的分数都是所有石子的分数贡献。
这里求了一个$min$和$max$，于是我们可以设计两个$f$数组，求出不同的分数。
注意边界问题和初始化，$max$和$min$要初始化为极大值或者极小值。
#include<bits/stdc++.h> using namespace std; int n,a[5005],b[5005],f[5005][5005]; int main() { ios::sync_with_stdio(false); cin>>n; for(int i=1;i<=n;i++)cin>>a[i]; for(int j=1;j<=n;j++)cin>>b[j]; for(int i=1;i<=n;i++) { int val=0; if(b[0]<a[i])val=f[i-1][0]; for(int j=1;j<=n;j++) { if(a[i]==b[j])f[i][j]=val+1; else f[i][j]=f[i-1][j]; if(b[j]<a[i])val=max(val,f[i-1][j]); } } int maxn=0; for(int i=1;i<=n;i++)maxn=max(maxn,f[n][i]); cout<<maxn<<" "; return 0; }
例2 NOIP2003 数字游戏
这道题首先仍然要断环成链，然后进行$O(n^4)$复杂度的$dp$，状态转移的过程仍然是在当前区间内寻找一个中间点（或者说断点），然后根据题目要求的$min/max$设计状态转移，这道题相比上一道题，看似更复杂，实际上不用考虑最后加一个前缀和，好理解很多，属于真正的区间$dp$入门。
#include<cstdio> #include<algorithm> #include<cstring> using namespace std; int n,m,maxn[105][105][15],minn[105][105][15],ma,mi,sum[105],a[105]; int mod(int a){return ((a%10)+10)%10;} int main() { scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) scanf("%d",&a[i]),a[i+n]=a[i]; for(int i=1;i<=2*n;i++) sum[i]=sum[i-1]+a[i]; memset(minn,0x7f7f7f7f,sizeof(minn)); for(int l=1;l<=2*n;l++) for(int r=1;r<=2*n;r++) maxn[l][r][1]=minn[l][r][1]=mod(sum[r]-sum[l-1]); for(int i=2;i<=m;i++) for(int l=1;l<=2*n;l++) for(int r=l+i-1;r<=2*n;r++) for(int k=l+i-2;k<r;k++) minn[l][r][i]=min(minn[l][r][i],minn[l][k][i-1]*mod(sum[r]-sum[k])),maxn[l][r][i]=max(maxn[l][r][i],maxn[l][k][i-1]*mod(sum[r]-sum[k])); mi=0x7f7f7f7f; for(int i=1;i<=n;i++) ma=max(ma,maxn[i][i+n-1][m]),mi=min(mi,minn[i][i+n-1][m]); printf("%d %d ",ma,mi); return 0; }
树形DP
全世界$DP$最菜的人居然在写树形$DP$的$Blog$，好耍了。
例1 没有上司的舞会
[传送门](https://www.luogu.org/problem/P1352)
这道题对应了树形$DP$的一个经典模型，就是关于$0/1$之间的树形$DP$，大概的模型为：
$f[u][1]+=max(f[v][1],f[v][0])$
第一维表示的是以节点$u$为根节点的子树，第二维表示选/不选。
#include<bits/stdc++.h> using namespace std; int n,f[12000][2],vis[6005],a[6005],h[12005],cnt; struct node{int v,nxt;}e[12005]; void add(int u,int v) { e[++cnt].v=v; e[cnt].nxt=h[u]; h[u]=cnt; } void dfs(int u,int fa) { f[u][1]=a[u]; for(int i=h[u];i;i=e[i].nxt) { int v=e[i].v; if(v==fa)continue; dfs(v,u); f[u][1]+=f[v][0]; f[u][0]+=max(f[v][0],f[v][1]); } } inline void read(int&x) { x=0;char c=getchar(); int f=1; while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();} while(c>='0'&&c<='9')x=x*10+c-'0',c=getchar(); x*=f; } int main() { read(n); for(int i=1;i<=n;i++)read(a[i]); for(int i=1;i<=n;i++) { int u,v; read(u),read(v); if(!u&&!v)break; vis[v]=true; add(u,v),add(v,u); } int rt; for(int i=1;i<=n;i++) if(!vis[i]){rt=i;break;} dfs(rt,0); printf("%d ",max(f[rt][0],f[rt][1])); return 0; }
例2 最大子树和
[传送门](https://www.luogu.org/problem/P1122)
很水的一道题，就是题意一点也不清晰。
#include<bits/stdc++.h> using namespace std; int n,a[200005],h[320005],cnt,f[320005],maxn,vis[320005]; struct node{int v,nxt;}e[320005]; void add(int u,int v) { e[++cnt].v=v; e[cnt].nxt=h[u]; h[u]=cnt; } void dfs(int u,int fa) { f[u]=a[u]; for(int i=h[u];i;i=e[i].nxt) { int v=e[i].v; if(v==fa)continue; dfs(v,u); f[u]+=max(f[v],0); } maxn=max(maxn,f[u]); } int main() { // freopen("testdata.in","r",stdin); scanf("%d",&n); for(int i=1;i<=n;i++)scanf("%d",&a[i]); for(int i=1;i<n;i++) { int u,v; scanf("%d%d",&u,&v); add(u,v),add(v,u); } dfs(1,0); printf("%d ",maxn); return 0; }
例3 选课
这道题是树上依赖背包的模板题。
我们可以这样思考:节点$u$的子树大小为$siz[u]$，那么在这棵树中我们最多能选出$siz[u]$个（当然要包含这个节点本身）节点作为答案的贡献，所以，这个节点对答案的贡献可以是$0$~$siz[u]$，那么我们可以设计状态$f[u][j]$用来表示在以$u$为根的子树中选$j$个节点的贡献， 针对每一个这个点的子节点，我们要么不选，要么选，选了这个点对应的情况就应该是，在节点$u$的子树中总共选择$j$个节点（$j$对应的遍历就应该是$siz[u]$~$0$），同时我们要选择子节点$v$，所以我们就还要在$v$节点的子树中选择一些节点，这个节点数是否可以直接看成$j-1$呢？不可以，因为剩下的$j-1$个节点在$u$和$v$的子树中分布不能肯定，所以就要单独枚举一维$k$，从$j-1$遍历到$0$，这一步应该是已经处理出来的，不要问我为什么，于是最终得到伪代码：
$ exttt{for j siz[u]...0}$
$ exttt{for k j-1...0}$
$ exttt{f[u][j]=max(f[u][j],f[u][j-k-1]+f[v][k]+w[v])}$
于是我们发现，这就是一个分组背包模型（虽然似乎好像应该可能也许大概有点变化）。
还剩下一个问题就是，为什么两维循环都是倒序的呢？
观察第一维度，我们倒序的时候，求出的$j$答案就是由大到小转移而来，如果我们按照顺序排序，前面已经更新过的$f$就会去更新后面的$f$，这就要出问题。
第二维倒序，思想源自$01$背包，保证不重复。
#include<bits/stdc++.h> using namespace std; int n,m,w[305],f[305][305],siz[305],h[305],cnt; struct node{int v,nxt;}e[605]; void add(int u,int v) { e[++cnt].v=v; e[cnt].nxt=h[u]; h[u]=cnt; } void dfs(int u,int fa) { siz[u]=1; for(int i=h[u];i;i=e[i].nxt) { int v=e[i].v; if(v==fa)continue; dfs(v,u); siz[u]+=siz[v]; for(int j=siz[u];j>=0;j--) for(int k=j-1;k>=0;k--) f[u][j]=max(f[u][j],f[u][j-k-1]+f[v][k]+w[v]); } } int main() { scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) { int fa; scanf("%d%d",&fa,&w[i]); add(fa,i),add(i,fa); } dfs(0,-1); printf("%d ",f[0][m]); return 0; }
状压DP
仔细想想，我讲不来状压DP，因为我也是个初学的萌新。
状压的核心就是，利用二进制位来枚举状态。
直接上题吧。
[SCOI2005]互不侵犯
题目描述:
在N×N的棋盘里面放K个国王，使他们互不攻击，共有多少种摆放方案。国王能攻击到它上下左右，以及左上左下右上右下八个方向上附近的各一个格子，共8个格子。（1<=N <=9, 0 <= K <= N * N）
分析:
这是一道状压的经典入门题。由于是矩阵，在状压的套路中要么枚举行要么枚举列，这里我们就枚举一波行数。
我们考虑，每一行有(1<<n-1)种状态，有合法也有不合法，我们不妨预处理一行中能出现的所有合法状态，那么针对行的合法状态是什么呢？就是不能相邻两个都为1，“都为1”我们显而易见能想到&运算。
如果有一个状态是i，如果i&(i<<1)的结果为1，那么就说明i这个状态是不合法的。为什么呢？举个例子:
有一个状态i为0110，人眼判断是不合法的，这个状态左移就应该是1100，两个状态相&，答案为真，所以状态i 0110就不合法。
所以我们就得到了预处理i是否合法的方法:i&(i<<1)。
下一步需要预处理出所有的状态数和每一个状态有多少个1（也就是说有多少个国王），这里也是位运算的知识qwq，于是我们可以得到:
for(int i=0;i<=(1<<n)-1;i++)//i表状态 { if(i&(i<<1))continue; s[++cnt]=i; num[cnt]=get(i); f[1][cnt][num[cnt]]=1; }
这当中有一个f数组是干什么的呢？我们设f[i][j][k]表示:到达第i行的状态j时，总共放了k个国王的方案数。
由于第一行不可以通过状态转移得到，所以我们预处理出来，如果这个状态合法，f[1][j][num[j]]的方案数就应该是1。
状态该怎么转移呢？第i行的某个状态应该由第i-1行的某个状态转移而来:
f[i][j][l]=f[i-1][k][l-num[j]]
只需要判断j和k这两个状态同时存在是否合法即可，合法才能进行转移，否则跳过。
不合法的判断:
if((s[j]&s[k])||((s[j]<<1)&s[k])||((s[k]<<1)&s[j]))continue;
Points:
这道题是求一个总方案数，一个新的状态可以由多种不同方案转移而来，所以新的状态要加上所有能转移出它的所有状态的方案数，这里的j和k都表示的是第几种状态，所以范围是1~cnt，而l至少应该等于num[j]，才能保证放的国王是足量的，也就是说在i,j状态时，总共放了l个国王，那么这肯定是l-num[j]的每一个状态转移而来的。
感觉自己说了好多废话..无所谓，能理解就行。
统计方案数就应该是最后一排每一个状态选了k个国王的总和，毕竟是统计总方案数。
代码:
#include<cstdio> #include<cstring> #include<algorithm> #define int long long using namespace std; int n,m,f[20][1<<10][105],s[1<<10],num[1<<10],cnt;//f[i][j][k] 第i行状态为第j种 这一行有k个国王 int get(int pos) { int ans=0; while(pos) { if(pos&1) ans++; pos>>=1; } return ans; } signed main() { scanf("%lld%lld",&n,&m); for(int i=0;i<=(1<<n)-1;i++)//i表状态 { if(i&(i<<1))continue; s[++cnt]=i; num[cnt]=get(i); f[1][cnt][num[cnt]]=1; } for(int i=2;i<=n;i++) for(int j=1;j<=cnt;j++) for(int k=1;k<=cnt;k++) { if((s[j]&s[k])||((s[j]<<1)&s[k])||((s[k]<<1)&s[j]))continue; for(int l=num[j];l<=m;l++) f[i][j][l]+=f[i-1][k][l-num[j]]; } int ans=0; for(int i=1;i<=cnt;i++) ans+=f[n][i][m]; printf("%lld ",ans); return 0; }
Matrix
题面不公开，在此做个小总结。
1.DP的核心思想是枚举，把我们要求但不能直接得到的决策进行枚举，适用于任何DP。
2.矩阵状压有个特色就是，存行或者列，枚举另一维的所有状态。
3.状压的核心思想是位运算，除此之外和普通DP差别不大，所以我们要熟练掌握各类位运算。
4.状压的过程当中常常会遇到很多的要求，要求不相邻等等，我们要学会把这些要求转化成位运算的代码。
5.初始化，状态与状态转移，这就是DP的过程 ，但我们只有找到了转移的方法，才知道每一个状态是怎么来的，自然也就知道了初始化。
#include<cstdio> #include<cstring> #include<algorithm> using namespace std; int n,m,chu[15],f[15][1050][1050],g[15][15],w[15][1050],fg[1050]; int main() { freopen("matrix.in","r",stdin); freopen("matrix.out","w",stdout); memset(f,0x7f7f7f7f,sizeof(f)); scanf("%d%d",&n,&m); int all=(1<<m)-1; for(int i=1;i<=n;i++) { char s[15]; scanf("%s",s+1); for(int j=1;j<=m;j++) chu[i]=(chu[i]<<1)|(s[j]-'0');//初始化每一行的状态 } for(int i=1;i<=n;i++) { for(int j=1;j<=m;j++) scanf("%d",&g[i][j]); for(int j=0;j<=all;j++) for(int k=1;k<=m;k++) if((j>>(m-k))&1)w[i][j]+=g[i][k]; //针对选择区间进行初始化 第i行的第j个状态进行初始化 } for(int i=0;i<=all;i++)fg[i]=(i|(i<<1)|(i>>1))&all;//初始化选择区间的覆盖区间 for(int i=0;i<=all;i++)f[1][fg[i]|chu[1]][i]=w[1][i];//i枚举的是选择区间 for(int i=1;i<=n;i++)//枚举第几行 for(int j=0;j<=all;j++)//枚举第i行的状态j for(int k=0;k<=all;k++)//枚举第j个状态的选择区间k { if((j&fg[k])!=fg[k])continue; for(int l=0;l<=all;l++)//枚举第i+1行的选择区间 { if((l|j)!=all)continue; f[i+1][chu[i+1]|k|fg[l]][l]=min(f[i+1][chu[i+1]|k|fg[l]][l],f[i][j][k]+w[i+1][l]); } } int ans=0x7f7f7f7f; for(int i=0;i<=all;i++) ans=min(ans,f[n][all][i]); printf("%d ",ans); return 0; }