poj2411解题报告

又是一道状态压缩动态规划的题目，于之前一道有异曲同工之妙，成功AC。
1.算法
(1)首先这道题目和之前的那道炮兵阵地类似，可以以行作为划分进行动态规划，后一行根据前一行的状态来确定。
(2)动态规划最重要的是找状态转移方程。就这道题来说，一共是n行，m列。我们可以这样考虑：我们一行一行的放1*2的牌，在第i行放完以后，必须保证该行所有的格子被填满了。这时记录下第i行向第i+1行凸出的地方。即如果有向第i+1行的凸出，就记录为1，否则记录0，这样就用一个m位的2进制数记录了第i行放完后的状态。比如说00110100就说明第2，4，5的位置向下凸出了。然后开始处理第i+1行，可以根据第i行记录的状态进行放牌。在放牌的时候就要将第i行记录为1的格子给空出来（因为这一个格子被第i行的一个牌占用了）。这样后一行的状态就根据前一行的状态来转移了。我们列出状态转移方程f[i][a]=sum{f[i-1][b]}（其中a为第i行填满以后向i+1行凸起的状态，b为i-1行填满以后向i行凸起的状态）剩下的任务是确定a和b之间的关系。
(3)要确定a,b之间的关系，我们首先要做的一件事情是，列举出一行可能出现的所有状态。在一行中放的牌分为两种情况，一种是这张牌的两格都在本行（横放），一种是这张牌的一格在本行，一个在上面一行或者下面一行（竖放）。我们将横放的牌填充的格子记作0，竖放的牌填充的格子记作1，这样，如001100100,（从右往左看）我们就可以断定第0，1格，第3，4格，第7，8格分别横放着一个牌，第2，5，6格分别竖放着一个牌。我们发现一个特点，横放的牌必须有偶数个0连在一起（原理很简单）。于是我们根据这个特点可以枚举出一行中所有可能的情况，并且把这些情况放到一个数组里，即s,用s_sum记录所有可能情况的个数，即数组的大小。生成s的过程是通过dfs（深搜）完成的。有了s，我们就可以确定状态转移方程中a，b的关系了。b是第i-1行向i行凸出的部分，于是我们遍历一下s，找出符合下列条件的状态s[x]：在b中为1的列上面必须要求s[x]也要为1(这样才能保证s[x]状态不于第i-1行冲突)。这样，a状态就是(s[x]-b)（原理：s[x]中的列为1的时候有两种情况，与上一行的1组成一个牌，或者与下一行的1组成一个牌，即向下凸出，用s[x]-b就减去了前一种情况，剩下的就是后一种情况了）
(4)说说代码：
(a)m,n用来记录输入的行列，s用来记录一行可能存在的所有情况，把一种情况的2进制表示压缩成一个int来表示。s_sum用来记录s数组的大小，即一共有多少种情况。f数组是记录状态的数组，第一个参数i是表示这是第i行填满后的状态，第2个参数x表示状态为x，f的值表示，这个得到这种状态有多少种方案。
(b)读取m,n，并对全局变量进行初始化(很重要，因为有多组测试用例)。（read_in函数）
(c)列出一行中可能有的所有状态，存放在数组s中，这个过程要调用dfs函数进行深度优先搜索。dfs的三个参数的意义，x为处理到第x列，data为当前的状态，num_of0表示前几列有多少个0（这个参数用来判断该列上可以设置的值）（creat_s函数）
(d)最重要的阶段要数dp动态规划了，首先用sum记录2的m次方用于下面的循环使用，然后是设置f数组第0行的值，所有可能的情况的值都为1。接着是通过状态转移方程得出所有f数组的值。最后返回f[n-1][0]，即最后一行排满后没有向后凸起的状态的方案数。将其打印。
2.实现
(1)对于f数组存放的值，因为可能较大，要将类型设置为long long,在最后输出的结果的时候要用%I64d来输出。
(2)n，m的位置是等价的，可以交换，把较小的作为n，较大的作为m。这样可以提高效率。
(3)注意变量的初始化，特别是多测试用例的题目。
(4)(((y)&(~s[x]))!=0)的运用很巧妙，可以判断是否符合y中有1的列对应的s[x]的该列也都为1。
3.代码

Problem: 2411		User: godfrey90
Memory: 336K		Time: 141MS
Language: C++		Result: Accepted

#include<cstdio>

int m, n;
int s[150];
int s_sum=0;
long long f[11][2048];

void read_in();
void creat_s();
long long dp();

int main() {
	read_in();
	while (!((m == 0) && (n == 0))) {
		creat_s();
		long long result = dp();
		printf("%I64d\n",result);
		read_in();
	}
	return 0;
}
void read_in() {
	scanf("%d%d", &m, &n);
	if (n > m) {
		int temp = m;
		m = n;
		n = temp;
	}

	for(int i=0;i<150;i++)s[i]=0;
	s_sum=0;
	for(int i=0;i<11;i++)
		for(int j=0;j<2080;j++)
			f[i][j]=0;
}
void dfs(int x, int data,int num_of_0) {
	if (x == m) {
		if(num_of_0%2==1) return;
		s[s_sum++] = data;
		return;
	}
	if (num_of_0%2==1) {
		dfs(x + 1, data,num_of_0+1);
	} else {
		dfs(x + 1, data,num_of_0+1);
		dfs(x + 1, data | (0X1 << x),num_of_0);
	}
}
void creat_s() {
	dfs(0,0,0);
}
long long dp(){
	int sum=1;
	for(int i=0;i<m;i++) sum*=2;

	for(int i=0;i<s_sum;i++){
		f[0][s[i]]=1;
	}
	for(int i=1;i<n;i++){
		for(int x=0;x<s_sum;x++){
			for(int y=0;y<sum;y++){
				if(f[i-1][y]==0) continue;
				if(((y)&(~s[x]))!=0)continue;
				f[i][s[x]-y]+=f[i-1][y];
			}
		}
	}
	return f[n-1][0];
}