状态压缩DP及其拓展

蒙德里安的梦想

题目 蒙德里安的梦想https://www.acwing.com/problem/content/293/

超级详细解析https://lishizheng.blog.csdn.net/article/details/112706309

 
/*
下文对  if ((j & k ) == 0 && st[ j | k] )  有清晰的解释！！！
*/
 
 
#include 
using namespace std;
 
 
const int N = 12, M = 1<< N;  
 
long long f[N][M] ;// 第一维表示列， 第二维表示所有可能的状态
 
bool st[M];  //存储每种状态是否有奇数个连续的0，如果奇数个0是无效状态，如果是偶数个零置为true。
 
vector<int > state[M];  //二维数组记录合法的状态
//vector> state(M);  //两种写法等价:二维数组
 
int m, n;
 
int main() {
 
    while (cin >> n >> m, n || m) //读入n和m，并且不是两个0即合法输入就继续读入
    { 
 
        //第一部分：预处理1
        //对于每种状态，先预处理每列不能有奇数个连续的0
 
        for(int i = 0; i < (1 << n); i ++) 
        {
 
            int cnt = 0 ;//记录连续的0的个数
 
            bool isValid = true; // 某种状态没有奇数个连续的0则标记为true
 
            for(int j = 0; j < n; j ++) //遍历这一列，从上到下
            { 
 
                 if ( (i >> j) & 1) 
                 {  
                     //i >> j位运算，表示i（i在此处是一种状态）的二进制数的第j位； 
                     // &1为判断该位是否为1，如果为1进入if
                    if (cnt & 1) 
                    { 
                    //这一位为1，看前面连续的0的个数，如果是奇数（cnt &1为真）则该状态不合法
                        isValid =false;
                        break;
                    } 
 
                    cnt = 0; // 既然该位是1，并且前面不是奇数个0（经过上面的if判断），计数器清零。
                    //其实清不清零没有影响
                 }
                 else cnt ++; //否则的话该位还是0，则统计连续0的计数器++。
            }
            if (cnt & 1)  isValid = false; //最下面的那一段判断一下连续的0的个数
 
            st[i]  = isValid; //状态i是否有奇数个连续的0的情况,输入到数组st中
        }
 
        //第二部分：预处理2
        // 经过上面每种状态 连续0的判断，已经筛掉一些状态。
        //下面来看进一步的判断：看第i-2列伸出来的和第i-1列伸出去的是否冲突
 
        for (int j = 0; j < (1 << n); j ++) //对于第i列的所有状态
        { 
            state[j].clear(); //清空上次操作遗留的状态，防止影响本次状态。
 
            for (int k = 0; k < (1 << n); k ++) //对于第i-1列所有状态
            { 
                if ((j & k ) == 0 && st[ j | k]) 
                // 第i-2列伸出来的 和第i-1列伸出来的不冲突(不在同一行) 
                //解释一下st[j | k] 
                //已经知道st[]数组表示的是这一列没有连续奇数个0的情况，
                //我们要考虑的是第i-1列（第i-1列是这里的主体）中从第i-2列横插过来的，
                //还要考虑自己这一列（i-1列）横插到第i列的
                //比如 第i-2列插过来的是k=10101，第i-1列插出去到第i列的是 j =01000，
                //那么合在第i-1列，到底有多少个1呢？
                //自然想到的就是这两个操作共同的结果：两个状态或。 j | k = 01000 | 10101 = 11101
                //这个 j|k 就是当前 第i-1列的到底有几个1，即哪几行是横着放格子的
 
                    state[j].push_back(k);  
                    //二维数组state[j]表示第j行， 
                    //j表示 第i列“真正”可行的状态，
                    //如果第i-1列的状态k和j不冲突则压入state数组中的第j行。
                    //“真正”可行是指：既没有前后两列伸进伸出的冲突；又没有连续奇数个0。
            }
 
        }
 
        //第三部分：dp开始
 
        memset(f, 0, sizeof f);  
        //全部初始化为0，因为是连续读入，这里是一个清空操作。
        //类似上面的state[j].clear()
 
        f[0][0] = 1 ;// 这里需要回忆状态表示的定义
        //按定义这里是：前第-1列都摆好，且从-1列到第0列伸出来的状态为0的方案数。
        //首先，这里没有-1列，最少也是0列。
        //其次，没有伸出来，即没有横着摆的。即这里第0列只有竖着摆这1种状态。
 
        for (int i = 1; i <= m; i ++) //遍历每一列:第i列合法范围是(0~m-1列)
        { 
            for (int j = 0; j < (1<//遍历当前列（第i列）所有状态j
            {  
                for (auto k : state[j])    // 遍历第i-1列的状态k，如果“真正”可行，就转移
                    f[i][j] += f[i-1][k];    // 当前列的方案数就等于之前的第i-1列所有状态k的累加。
            }
        }
 
        //最后答案是什么呢？
        //f[m][0]表示 前m-1列都处理完，并且第m-1列没有伸出来的所有方案数。
        //即整个棋盘处理完的方案数
 
        cout << f[m][0] << endl;
 
    }
}   

小国王【线性状压DP+滚动数组优化+目标状态优化】  

题目 小国王http://ybt.ssoier.cn:8088/problem_show.php?pid=1592

解析 https://www.acwing.com/solution/content/56348/

 

#include
using namespace std;
const int N=12,M=1<
int cnt;//同一行合法状态的个数 
int s[M];//同一行合法状态集 
int num[M];//每个合法状态包含国王个数 
long long f[N][C][M];  //f[i][j][a] 表示前i行放了j个国王，第i行第a个状态时的方案数	 
int main()
{
	int n,k;//棋盘行数 国王总数 
	cin>>n>>k;
	for(int i=0;i<(1<//枚举一行所有状态 
	{
		if(!(i&i>>1))//如果不存在相邻的1 
		{
			s[cnt++]=i;//保存一行的合法状态 
		}
		for(int j=0;j
		num[i]+=(i>>j&1);//	统计每个合法状态的国王数量 
	}
	f[0][0][0]=1;//不放国王也是一种方案 
	for(int i=1;i<=n+1;i++)//枚举行 
	for(int j=0;j<=k;j++)//枚举国王数 
	for(int a=0;a//枚举第i行的合法状态 
	for(int b=0;b//枚举第i-1的合法状态 
	{
		int c=num[s[a]];//第i行第a个状态的国王数 
		if((j>=c)&&!(s[b]&s[a])&&!(s[b]&(s[a]<<1))&&!(s[b]&(s[a]>>1)))//如果不存在同列的1、斜对角的1，可以继续放国王 
		f[i][j][a]+=f[i-1][j-c][b];//从第i-1行向第i行转移 
	}
	cout<1][k][0]<//第n+1行什么都不放，相当于只在1~n行放国王 
}

玉米田【线性状压DP】

 题目 玉米田 https://www.acwing.com/problem/content/description/329/

 题解https://www.acwing.com/solution/content/56822/

 

 

更新

#include
using namespace std;
const int N=14,M=1<1e8;
int f[N][M];
int g[N];
int s[M];
int cnt;
int main()
{
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    for(int j=1;j<=m;j++)
    {
        int x;
        cin>>x;
        g[i]=(g[i]<<1)+x;
    }
    
    for(int i=0;i<(1<
    {
        if(!(i&i>>1))
        s[cnt++]=i;
    }
    f[0][0]=1;
    for(int i=1;i<=n+1;i++)
    for(int a=0;a
    for(int b=0;b
    {
        if((s[a]&g[i])==s[a]&&!(s[a]&s[b]))
        f[i][a]=(f[i][a]+f[i-1][b])%mod;
    }
    cout<1][0]<
}

 炮兵阵地 

题目  炮兵阵地

解析 

#include
using namespace std;
const int N=110,M=1<<10;
int f[2][M][M];
int g[N];
vector<int> state;
int cnt[M];
int n,m;
 
bool check(int s)
{
    for(int i=0;i
        if((s >> i & 1)&&((s>>i+1&1)||(s>>i+2&1)))
            return false;
    return true;
}
int count(int s)
{
    int res=0;
    while(s)
    {
        res+=s&1;
        s>>=1;
    }
    return res;
}
int main()
{
    cin>>n>>m;
    for(int i=0;i
    for(int j=0;j
    {
        char a;
        cin>>a;
        if(a=='H')g[i]+=1<
    }
    for(int i=0;i<1<
    {
        if(check(i))
        {
            state.push_back(i);
            cnt[i]=count(i);
        }
    }
    
    
    for(int i=0;i2;i++)
        for(int j=0;jsize();j++)
            for(int k=0;ksize();k++)
                for(int u=0;usize();u++)
                {
                    int a=state[u],b=state[j],c=state[k];
                    if((a&b)||(a&c)||(b&c))continue;
                    if(g[i]&c)continue;
                    f[i&1][j][k]=max(f[i&1][j][k],f[i-1&1][u][j]+cnt[c]);
                }
    cout<1&1][0][0]<
}

 愤怒的小鸟

题目 愤怒的小鸟

解析

#include
using namespace std;
#define x first
#define y second
#define db double
const int N=20,M=1<<18;
const db eps=1e-6;
typedef pair pdd;
int f[M];
pdd q[N];
int n,m;
int path[N][N];/
bool cmp(db x,db y)//因为浮点数会失精度，用来判断两个数是否相等
{
    if(fabs(x-y)return true;
    return false;
}
int main()
{
   int T;
   cin>>T;
   while(T--)
   {
       cin>>n>>m;
       for(int i=0;i>q[i].x>>q[i].y;
       memset(path,0,sizeof path);//清空上一维的状态
       for(int i=0;i
       {
           path[i][i]=1<//自己与自己的抛物线能打自己，避免有时候只有一个点占一条抛物线
           for(int j=0;j
           {
               db x1=q[i].x,y1=q[i].y;
               db x2=q[j].x,y2=q[j].y;
               if(cmp(x1,x2)) continue;//判断相不相等，假如相等这条抛物线不存在
               db a=(y1/x1-y2/x2)/(x1-x2),b=y1/x1-a*x1;
               if(a>0||cmp(a,0.0)) continue;//开口向下，所以a<0
               for(int k=0;k//枚举这条抛物线能打到的其他点
               {
                   db x=q[k].x,y=q[k].y;
                   if(cmp(a*x*x+b*x,y)) path[i][j]+=1<//假如这个点在抛物线上，则加到这个ij点的状态下
               }
           }
       }
       memset(f,0x3f,sizeof f);//清空上一维的数，因为要最小值，所以初始化为正无穷
       f[0]=0;//这也是个合法的状态，初始化为0
       for(int i=0;i<1<//枚举每一个状态
       {
           int x=0;
           for(int j=0;j//找这个状态中没有猪的位置，也就是0的位置
             if(!(i>>j&1))
             {
               x=j;
               break;
             }
            for(int j=0;j//更新一下这个状态i与这只猪的状态下的最小值
              f[i|path[x][j]]=min(f[i|path[x][j]],f[i]+1);
       }
       cout<1<-1]<//输出所有猪打完的最小值，也就是所有位置都是1的状态
   }
    return 0;
}

宝藏----待更新