又是一道状态压缩动态规划的题目,于之前一道有异曲同工之妙,成功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];
}
分享到:
相关推荐
poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题...
poj 3414解题报告poj 3414解题报告poj 3414解题报告poj 3414解题报告
poj 1012解题报告poj 1012解题报告poj 1012解题报告poj 1012解题报告
poj 2329解题报告poj 2329解题报告poj 2329解题报告poj 2329解题报告
poj 1440解题报告 poj 1440解题报告 poj 1440解题报告 poj 1440解题报告
poj 3083解题报告poj 3083解题报告poj 3083解题报告poj 3083解题报告
poj 1659解题报告poj 1659解题报告poj 1659解题报告poj 1659解题报告
里面有非常详细的对于POJ 2411的解题报告,相信对于初学动态规划和深度优先搜索的同学来说有很好的帮助作用。
poj 3720解题报告poj 3720解题报告poj 3720解题报告poj 3720解题报告
poj1691解题报告 题目来源:http://acm.pku.edu.cn/JudgeOnline/showproblem?problem_id=1691(POJ No.1691) 解法: 搜索
poj2828解题报告,希望能帮到志同道合的算法爱好者
北大poj解题报告,希望能帮到软件工程的同学,每天一道,持之以恒,熟能生巧,与您共勉!
北大ACM1316解题报告
Problem 1061 青蛙的约会 poj解题报告。有源码。可直接提交C++实现
这是我发的第二篇解题报告,写的不怎么的。呵呵!!!!!
ACM Poj Pku 解题报告答案 打包 下载 600多题 史上最全 不是网上乱传的200多题,更不是100多题就挂着10分才能下的题 下了这个 大家也不要浪费分数去下载其它版本的了,基本上都有 共享 一起进步 中国加油 ACMer...
ACM POJ 解题报告北大POJ 大量解题代码
本人整理的POJ解题报告,一共有250道题
北大ACM在线评测系统POJ的题目解题报告。涵盖各种类型的acm题目。值得参考借鉴。打包下载。
不错的资源 收集了网上的一些解题报告 方便同学们学习参考