关于状态压缩DP以及状态压缩

首先要明确：状态压缩是利用数字来代表一组序列的方法，从而降低序列访问的复杂度，本质上跟HASH有着差不多的思想，但是其实就是数位运算的一种

定义：集合中共有N个数字，其中每个数字均小于K，能么我们可以用N位K进制数来表示整个集合，能么该数字转化为十进制数字（也就是int or long long），整个状态的表示就变成了一个数字

状态的表示i实际上就是利用数字来扩充代表的范围

最典型的一道例题：

USACO 06 corn fields

题目中给定一个N*M的矩阵，其中1代表可操作，0代表不可操作

让你选择其中可操作的点，问给定的矩阵中，两两选定的点不相邻的选择方案数一共有多少种

这是一道非常非常典型的状态压缩DP的问题，阶段可以表示为每一行，其中状态表示当前行中被选定的合法的被操作的点的集合！

其中预处理每行中每种情况的合法性，以及每种情况与每行中能被操作的点的合法性的处理

 /* USACO 06 Corn Fields */

 #include <bits/stdc++.h>
 using namespace std;

 const int MOD=(int)1e9;

 ][];
 /* 4096表示为状态压缩 */
 ][];
 ];
 /* 每行的状态Field的状态 */
 ];
 int n, m;

 int main(){
     cin>>n>>m;
     ;i<=n;i++)
         ;j<=m;j++)
             cin>>Field[i][j];

     ;i<=n;i++)
         ;j<=m;j++)
             Fline[i]=(Fline[i]<<)+Field[i][j];

     <<m;
     ;i<MAX;i++)
         state[i]=(!(i & (i<<)) && !(i & (i>>)));
     /* for(int i=0;i<MAX;i++)
         cout<<state[i]<<" ";
     cout<<endl; */

     dp[][]=;
     ;i<=n;i++)
         ;j<MAX;j++)
             if(state[j] && ((j&Fline[i])==j))
                 ;k<MAX;k++)
                     )
                         dp[i][j]=(dp[i][j]+dp[i-][k])%MOD;

     /* for(int i=1;i<=n;i++){
         for(int j=0;j<MAX;j++)
             cout<<dp[i][j]<<" "; */
         /* cout<<endl;
     } */

     ;
     ;i<MAX;i++) ans=(ans+dp[n][i])%MOD;

     cout<<ans;

     ;
 }

巴特西

关于状态压缩DP以及状态压缩

最新文章

热门文章