状压DP:超详细一道入门题详解,大家一同进步! [YbtOJ/USACO]

Source

题目链接:
洛谷题目入口
/YbtOJ-高效进阶-状压dp-A.【例题1】 种植方案

解析在代码里:

#include <bits/stdc++.h>
using namespace std;
const int Mod = 1e8;
int m, n, f[13][4097], F[13];
bool field[13][13];
bool state[4097];
// max state: (111111111111)2 =(2^12)10 = (4096)10

int main()
{
    
      
	scanf("%d%d",&m,&n);
    for (int i = 1; i <= m; i++)
        for (int j = 1; j <= n; j++)
			scanf("%d",&field[i][j]);
//

    for (int i = 1; i <= m; i++)
        for (int j = 1; j <= n; j++)
            F[i] = (F[i] << 1) + field[i][j];
// 	F[i]:保存第i行的艹地肥沃情况为二进制数,方便后续处理

    int MAX_STATE = 1 << n;
	//二进制中有n位,对于十进制表现为有2^n大的总方案数
    for (int i = 0; i < MAX_STATE; i++)
        state[i] = ((i&(i<<1))==0) && ((i&(i>>1))==0);
//  记录所有可分配方案:枚举所有小于总方案数的十进制数字,
//  判断其转化为二进制后显示的方案是否可行,行则state[i]为ture
//
//  具体地:使该方案整体左移,若&的结果为零,则没有任何
//  选择的土地向左的临近被选择。向右同理。
//
//  *举例:当该块土地被选择时,对应的该二进制数的该位为1,则
//  10101显然为一个合理方案: //  11001显然为一个不合理方案:
//	  010101                 //    011001
// 	& 101010(此处为左移情况) //  & 110010(此处为左移情况)
//  = 000000                 //  = 010000

	f[0][0] = 1;
    for (int i = 1; i <= m; i++){
    
      //枚举每行
    	for (int j = 0; j < MAX_STATE; j++){
    
      //枚举所有可能方案
    		if (state[j] && ((j & F[i]) == j)){
    
      
			//state[j]判定该方案j可行
			//&&之后的部分判定方案j所选的草地是否足够肥沃
			//
			//*举例:已知,经过前面state的确认,
			//此时j表示的是一个可行的二进制方案,则
			//如有j=21(10)=10101(2),F[i]=29(10)=11101(2)
			//  10101 = j
			//& 11101 = F[i]
			//= 10101 = j
			//借助按位与(&)的性质,我们发现:
			//当j为1的数位与F[i]同为1时,二者&的结果为j。
			//
			//至此,我们完成了对该方案j可行性的判定。
				
    			for (int k = 0; k < MAX_STATE; k++){
    
      
					//再枚举每种可能方案从上一行进行状态转移
    				if ((k & j) == 0){
    
      
						//这里意思是:k与j每一位都不同
						//因为上下也算是相邻
						//保证继承的上一行的方案数是与自己匹配的
						//不然不不就不符题意了嘛
						//还搞不懂就这回自己举例

    					f[i][j] = (f[i][j] + f[i-1][k]) % Mod;
    					//继承上一行的可能方案为k的方案数
						//如果上一行的该方案不符合要求,那么加了也没值
						//第一行只能从f[0][0]得到第一行属于自己的那份方案数
						//此后每一行得以继承上一行所有与自己匹配的方案的值(if中的条件)
						
					}
				}
                    
	        }
                
	    }
            
   	}

	int ans = 0;
    for (int i = 0; i < MAX_STATE; i++)
        ans = (ans + f[m][i]) % Mod;
	//方案数由上一行继承过来
	//那么最终答案就都在最后一行啦
	//把最后一行统计至此的方案数全部加起来就好啦!
	
    printf("%d\n",ans);
    return 0;
}