menu Stephen Space
more_vert
chevron_right 首页 » 【OI】 » 正文
【OI】OI日记 · 8月5号——状压DP
2020-08-05 | 【OI】 | 暂无评论 | 46 次阅读 | 603字

    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!我们明天见!!!

None
发表评论
暂无评论
textsms
account_circle
email
link