DP第三天,我整个人都傻了。。。今天在洛谷上翻了一下,发现所有蓝题难度以上的题目都涉及到动态规划,所以这块硬骨头一定要啃下来!!!
今天学习的是状压DP。DP就不讲了,我们主要来聊聊状压。状压就是利用了计算机处理二进制速度为O(N)的优势来用一个数字的二进制模拟一个bool数组,从而实现状态压缩的目的。
状态压缩涉及到位运算,我们一起来回顾一下。
基本运算
1.与
与的运算符为&
,你也可以写成and
。意思是两个数字相与,对应位都是1,结果为1,反之为0。举个例子
1001111010101
& 0110110010011
-----------------
0000110010001
2.或
或的运算符为|
,你也可以写成or
。意思与与相反,也就是都是0则为0,反之为1。举个例子
10010101011000
| 00101101001110
------------------
10111101011110
3.异或
异或的运算符为^
(我根本就不知道这个东西怎么打出来),亦可写作xor
。意思是相同为1,不同为0。举个例子
1000110111010
^ 0110101110001
-----------------
0001100110100
4.取反
取反的符号是~
,顾名思义就是将0变1,1变0。举个例子
~01101101010=10010010101
5.左移和右移
左移和右移的符号分别是<<
和>>
。意思是将二进制串整体左移。空缺的部分补0。那么,语法是什么?n<<m
表示把n左移m位。反之亦然。我们举个例
1<<5 = 32
等同于把1左移5位变成100000
64>>3 = 8
等同于把1000000右移3位变成1000
好,基础知识复习完了,接着讲状压DP。状压DP一般是定义$f[i]$,i表示状态。所以基本没有一般形式,不同题目需要根据需要自己添加维度。下面来做一下题吧。
给定一张n;($n \leq 20$)个点的带权无向图,编号为0~n1问从0到n1的最短hamilton距离。
hamilton路程定义是从0到n-1不重不漏地经过每个店恰好一次。
输入格式:输入$M,N$,接着是$M*N$的邻接矩阵表示边权
输出格式:一行,输出最短路径长度。
那么,这道题我们设两个维度。设定$f[i][j]$为状态为i时,此时在j点的最短路径。所以就有了转移方程:
$$ f[i][j]=min(f[i][j],f[i<<(k-1) and (i)][k]+1); $$
在这之中,i循环每一种状态,状态这样定义:1为已经走过,0为未走过。j和k表示从k走到j。在这之前。在这之前,f数组要初始化。如何初始化见程序:
#include <bits/stdc++.h>
using namespace std;
int n,m;
int edge[25][25];
int f[1<<21][25];
int main()
{
cin>>n>>m;
for (int i=1;i<=m;i++)
{
int tmp1,tmp2;
cin>>tmp1>>tmp2;
edge[tmp1][tmp2]=1;
}
//i:走没走过;j:当前点
for (int i=1;i<=n;i++)
f[1<<(i-1)][i]=0;
for (int i=1;i<=(1<<n-1);i++)
{
for (int u=1;u<=n;u++)
{
for (int v=1;v<=n;v++)
{
if ((1<<(u-1)) and i && (1<<(v-1)) and i && edge[u][v])
f[i][u]=min(f[i][u],f[i<<(v-1) and i][v]+edge[u][v]);
}
}
}
int ans=INT_MAX;
for (int i=1;i<=n;i++)
ans=min(ans,f[1<<n-1][i]);
cout<<ans<<endl;
return 0;
}
最后,放上今天的做题记录o( ̄▽ ̄)ブ
OK!我们明天见!!!