状压DP

状态压缩，一种优化。

快速判断是否为状压带派

首先看到数据范围，如果有变量较小，且为什么集合问题，放置问题，排列问题，差不多都为状压带派。

状压套路

常见的状压一般存本行会波及的行的状态，第几行等等。

可以用一个动态数组 $ans$ 来记录合法的一行的状态，然后基本只用循环 $ans$ ，再判断多行之间是否合法

一般的状态压缩，前几行都是要自己初始化的。

要注意是否需要从 $0$ 开始。

状态压缩常用命令

CPP

__builtin_popcount(i) 找出i里面有几个数位为1,适用与int

__builtin_popcountll(i) 找出i里面有几个数位为1,适用与long long

i|=(1<<j) 设置第j位为1

i&=~(1<<j) 设置第j位为0

// 检查第j位是否为1
if (i & (1 << j)) {
    // 第j位为1
}

// 检查第j位是否为0
if (!(i & (1 << j))) {
    // 第j位为0
}

例题1

题目

dp_{i,j,k} \to \text{表示前i行,j个国王,第i列状态为k,的方案数}

转移方程为

dp_{i,j,k}=dp_{i,j,k}+dp_{i-1,j-num_k,o}\\ i \to 第几行\\ j \to 几个国王\\ k \to 第i行的状态\\ num_k \to k中1的个数\\ o \to 第i-1行的状态\\

CPP

#include<bits/stdc++.h>
#define int long long 
using namespace std;
int n,m;
int dp[11][105][(1<<10)+5];
int num[(1<<10)+5];
vector<int>ans;
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
	cin>>n>>m;
    for(int i=0;i<(1<<n);i++){
        if((i&(i>>1))==0&&(i&(i<<1))==0){
            ans.push_back(i);
            num[i]=__builtin_popcount(i);
        } 
    }
    for(auto i:ans)
	    if(num[i]<=m)
	        dp[1][num[i]][i]=1;
    for(int i=2;i<=n;i++){
    	for(int l=0;l<=m;l++)
        	for(auto j:ans)//当前这一行
        	    for(auto k:ans){//上一行
         	       if((k&j)==0&&((j>>1)&k)==0&&((k>>1)&j)==0&&num[j]<=l)
						dp[i][l][j]+=dp[i-1][l-num[j]][k];
           		}   
    }	
    int sum=0;
    for(auto i:ans){
       sum+=dp[n][m][i];
    }
    cout<<sum;
    return 0;
}

例题2

题目

这道题目也较为好想，但~~难以调教~~。

首先，把行内合格的状态处理出来加到

ans

数组里面。

很明显，我们要枚举

3

行装态，与第几行开始。

状态定义

dp_{i,j,k]} = \text{在第 } i \text{ 行状态为 } j \text{，第 } i-1 \text{ 行状态为 } k \text{ 时的最大炮兵数量}

状态转移方程

dp_{i,j,k} = \max(dp_{i,j,k},dp_{i-1,k,o} + \text num_j)

约束条件

地形约束： $j \& a[i] = 0$
相邻行约束： $j \& k = 0$
隔行约束： $j \& o = 0$
行内约束： $(i \& (i \ll 1)) = 0 \land (i \& (i \ll 2)) = 0$

变量说明

$i$ ：当前行号 $(3 \leq i \leq n)$
$j$ ：当前行状态 $(j \in S)$
$k$ ：上一行状态 $(k \in S)$
$o$ ：上两行状态 $(o \in S)$
$\text{num}[j]$ ：状态 $j$ 的炮兵数量 $(\text{popcount}(j))$
$a[i]$ ：第 $i$ 行地形掩码
$S$ ：所有合法状态的集合

初始化

当

n = 1

时：

dp_{1,j,0} = num_j,\quad \forall j \in S \land j \& a_1 = 0

当

n \geq 2

时：

dp_{2,j,k} = num_j + num_k,\quad \forall j,k \in S \land j \& k = 0 \land j \& a_2 = 0 \land k \& a_1 = 0

最终答案

\text{ans} = \max_{j,k \in S} dp_{n,j,k}

代码

CPP

#include<bits/stdc++.h>
using namespace std;
const int N=1000;
int dp[1005][1<<N][1<<N];
int n,m;
int a[105];
int num[1<<N];
int ans=0;
vector<int>anss;
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
    cin>>n>>m;
    for(int i=1;i<=n;i++){
    	string s;
    	cin>>s;
    	for(int j=0;j<m;j++){
    		if(s[j]=='H'){
    			a[i]|=(1<<j);
			}
		}
	}
	for(int i=0;i<(1<<m);i++){
		if(((i&(i<<1))==0)&&((i&(i<<2))==0)){
            anss.push_back(i);
            num[i]=__builtin_popcount(i);
        }
	}
	if(n==1){
		for(int i:anss){
			if((i&a[1])==0){
	            dp[1][i][0]=num[i];
	            ans=max(ans,dp[1][i][0]);
	        }
		}
        cout<<ans;
        return 0;
	}
	//cout<<anss.size();
	for(int i:anss){
		for(int j:anss){
			if(((j&i)!=0)||((i&a[2])!=0)||((j&a[1])!=0))continue;
			dp[2][i][j]=num[i]+num[j];
			ans=max(ans,dp[2][i][j]); 
		}
	}
	for(int i=3;i<=n;i++){
		for(int j:anss){//这一行 
			if(((j&a[i])!=0))continue;
			for(int k:anss){//上一行 
				if(((j&k)!=0)||((k&a[i-1])!=0))continue;
				for(int o:anss){//上两行 
					if(((o&k)!=0)||((o&j)!=0)||((o&a[i-2])!=0))continue;
					dp[i][j][k]=max(dp[i][j][k],dp[i-1][k][o]+num[j]);
					ans=max(ans,dp[i][j][k]);
				}
			}
		}
	}
//	for(int k=2;k<=n;k++)
//		for(int i:anss){
//			for(int j:anss){
//				cout<<dp[k][i][j]<<" ";
//			}
//			cout<<endl;
//		}
	cout<<ans;
    return 0;
}

文章操作

快速判断是否为状压带派

状压套路

状态压缩常用命令

例题1

例题2

状态定义

状态转移方程

约束条件

变量说明

初始化

最终答案

代码

相关推荐

评论

状压DP