状压DP-学习笔记

FDOI · 2025-04-13 13:14:42 · 算法·理论

状压介绍：

核心思想：

状态压缩，顾名思义，把一个复杂度状态压缩，使其用一个二进制数表示。

比如选数，二进制数10010 表示第二个和第五个数字被选上。

一般我们使用位运算来处理相关操作。

定义状态：

一般情况下，状态压缩有一维是二进制，表示当前的选择方案，对于某些问题，需要有顺序，那么第一位会记录当前选到了哪个。

比如 dp[2][1] 表示目前选到第二个数了，其中第一个被选中。

循环：

拿二维来说，定义一个二维循环：

    for(int i=1;i<=n;i++)
        for(int j=0;j<(1<<n);j++)

其中第一层，i表示当前遍历到的编号（由1到n），而内层的 j 表示当前选择的方案，如当前 j 为 4时，此时转化为二进制数 100 表示此时方案中只有第3个数被选上，由于对于 n 个数而言，有 n^2 种方案，因此j从 0 （都不选）循环到 (1<<n) （全选），当然，这还是需要按照实际情况调整的。

对于无序的题目，定义一维，遍历 j 即可。

判断、操作方式：

对于状压DP，我们需要进行一些处理和操作：

以如下代码为例：

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n;
double x[221],y[120],ans=1e10;
double dp[21][41000];
double dist(int a,int b){
    return sqrt((x[a]-x[b])*(x[a]-x[b])+(y[a]-y[b])*(y[a]-y[b]));
}
signed main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>x[i]>>y[i];
    }
    memset(dp,0x7f,sizeof(dp));
    for(int k=1;k<=(1<<n)-1;k++){
        for(int i=1;i<=n;i++){
            if(k&(1<<i-1)==0) continue;
            if(k==(1<<i-1)){
                dp[i][k]=0;
                continue;
            }
            for(int j=1;j<=n;j++){
                if((k&(1<<(j-1)))==0||i==j) continue;
                dp[i][k]=min(dp[i][k],dp[j][k-(1<<i-1)]+dist(i,j));
            }
        }
    }
    for(int i=1;i<=n;i++){
        ans=min(ans,dp[i][(1<<n)-1]+dist(i,0));
    }
    printf("%.2f",ans);
    return 0;
}

k & (1 << (i - 1)) == 0判重

k == (1 << (i - 1))判断边界条件

(k & (1 << (j - 1))) == 0 || i == j 避免重复访问

这些操作的意义十分明了，所以可以根据需要来自我处理。

状压的使用场景：

1.有关子集等需要枚举全部子集方案。
2.求排列组合的方案。
3.棋盘防止等相关问题。
4.图上路径问题。