卫戴五点击即看

状压DP

状压$DP$，是状态压缩动态规划的简称，顾名思义，我们要做的就是把复杂状态压缩为一个简单的部分，如果你是按照顺序看的《从入门到入土(真)---DP一文通》，可以发现多重背包问题中的二进制划分优化也是一种状态压缩

状压$DP$的核心在于将复杂的不好表示的状态压缩以便于使用与枚举，最常见也是最常用的状压方式就是二进制划分

---

对于这种特殊的$DP$，多说无益，还是老样子上一道最简单的例题：国王

思考一下在不压缩状态的情况下怎么安排，安排个gui！这根本写不了是不是，我怎么知道怎么表示国王？

所以我们考虑将每行放置国王这个状态使用$01$串压缩下来，对于第$i$位为$1$就标志这在第$i$列放置了一个国王，这只需要枚举一遍就行

vector< int > state;//保存合法状态，免去每次都进行O(1<<n)的状态枚举
for( int i=0;i<( 1<<n );i++ )//枚举所有状态
{
    if( ( i << 1 ) & i) continue;//存在相邻的1(相邻国王互斥)，状态不合法
    state.push_back( i );//放入合法状态
}

这个时候，每一个$state$就代表了一个合法的状态，并且因为压缩成了一个整型，所以十分方便我们枚举$DP$

f[0][0][0]=1;
for( int i=1;i<=n+1;i++ )//当前正在考虑第i层
{
    for ( int j=0;j<=k;j++ )//前i层一共要放j个国王
    {
        for ( auto now:state )//枚举当前层的状态
        {
            int ones=__builtin_popcount( now );//__builtin_popcount仅支持gcc环境下的快速O(1)返回一个数二进制状态下一个数的函数
            if ( ones > j ) continue;//当前行要放的国王比总数还多了，不合法
            for ( auto lst:state )//枚举上一行的状态，因为当前行的合法性受上一行的制约
            {
                if ( now & lst ) continue;//出现同一列的国王，不合法
                if ( now & ( lst << 1 ) ) continue;//第i行的国王右上角存在国王，不合法
                if ( ( now << 1 ) & lst ) continue;//第i行的国王左上角存在国王，不合法
                f[i][j][now]+=f[i-1][j-ones][lst];//转移
            }
        }
    }
}
cout<<f[n+1][k][0];

这里我们使用了一个状压$DP$常用的小技巧，我们会钦点虚拟行$0$和$n+1$以便于我们进行$DP$，因为如果不这样做，我们就需要单独枚举第一行的状态，统计答案时还要枚举最后一行的状态，十分麻烦

听到这里，状压$DP$的过程也呼之欲出了：$确定如何压缩状态->枚举合法状态并保存->钦定虚拟行->$

$枚举当前位置状态->枚举会影响当前位置合法性的位置->DP转移->输出答案$

状压$DP$思维难度不高，主要是代码实现与卡空间上，这时要注意尽量不要产生数组或状态的浪费

恭喜你又学会了一类$DP$!!!

---

轮廓线DP

轮廓线$DP$，最常用的是插头$DP$(将轮廓线上的状态设置为四连通的插头)，是一种可以有效优化状压$DP$时间复杂度的手段

拿一道例题来举例：「一本通 5.4 例 2」牧场的安排

先看看我们最初的代码是怎样写的

for( int i=1;i<=n+1;i++ )
    {
        for( auto now:state )
        {
            if( now & mp[i] ) continue;
            for( auto lst:state )
            {
                if( now & lst ) continue;
                f[i][now]=( f[i][now]+f[i-1][lst] )%p;
            }
        }
    }

枚举上一行的状态与这一行的状态以转移是吧，易得时间复杂度是枚举行数乘上两次枚举状态$O(n\times 2^{n}\times 2^{n})$

当$n\leq 12$的时候能过，但是如果我们把限制增大至$n\leq 20$呢，这个方法就会倒闭

考虑我们的时间都花销在哪里了->枚举状态对吧，那么有没有方法省去每次枚举两行的状态呢

有的兄弟有的，像这么强的$DP$方法就是轮廓线的$DP$

轮廓线$DP$顾名思义就是只枚举轮廓线的状态，如图

在这里，我们会只关注最后$n$个格子的状态进行转移，从而大大的节省时间，将本题的时间复杂度压缩到了$O(n\times 2^n)$

核心代码如下：

f[0][0]=1;
for( int i=0;i<n;i++ )
	for( int j=0;j<m;j++ )//最好不要浪费空间，从二进制第一位开始使用
	{
		memset( f[i^1],0,sizeof( f[i^1] ) );//因为只与i-1行有关，所以滚动数组优化
		for( int k=0;k<( 1<<m );k++ )
		{
			int up=( 1<<j )&k;
			int left=0;
			if( j ) left=( 1<<( j-1 ) )&k;//解压出左边与上边
			if( !i && up ) continue;//第1行上面没有放置的方法
			if( !j && left ) continue;//最左边的左方没有放置的方法
			if( up && left )//上面选了，左边选了，这个点不能选
			{
				f[i^1][k^( 1<<j )]=( f[i^1][k^( 1<<j )]+f[i][k] )%p;
				continue;
			}
			if( left )//左边选了，这个点不能选
			{
				f[i^1][k]=( f[i^1][k]+f[i][k] )%p;
				continue;
			}
			if( up )//上面选了，这个点不能选
			{
				f[i^1][k^( 1<<j )]=( f[i^1][k^( 1<<j )]+f[i][k] )%p;
				continue;
			}
			if( !mp[i][j] )//障碍不能选
			{
				f[i^1][k]=( f[i^1][k]+f[i][k] )%p;
				continue;
			}
			//除去以上的确定状态，讨论选与不选两种情况
			f[i^1][k]=( f[i^1][k]+f[i][k] )%p;
			f[i^1][k^( 1<<j )]=( f[i^1][k^( 1<<j )]+f[i][k] )%p;
		}
	}

温馨提示：所有强制轮廓线$DP$的题目(意为必须用轮廓线不然会$T$的题目)全部是黑题($NOI/NOI+/CTSC$)