Corn Fields
题目来源:
http://poj.org/problem?id=3254
题目大意:一个人买了一个N*M个方格组成的农场,有部分方格不能种植。现在需要种草给牛吃,而牛又不喜欢挨着吃(don’t share an edge–>两个方格无公共边),不种草也算一种方案,求种植方案数。
此题与Mondriaan's Dream 类似,就不多讲了。
#include <iostream>
#include <memory.h>
#define MOD 100000000
using namespace std;
const int maxn=15;
int isFertile[maxn][maxn];
int f[maxn][1<<maxn];
int n,m;
void dfs(int s,int p,int *a,int &tail,int row)
{
if(p==m)
{
int k;
for(k=0;k<m;k++)
{
if(s&(1<<k)&&(isFertile[row][k]==0||(s&(1<<(k+1))))) break;
}
if(k>=m)
{
a[tail++]=s;
}
return ;
}
if((s&(1<<p))==0) {dfs(s,p+1,a,tail,row);}
else
{
dfs(s,p+1,a,tail,row);
dfs(s^(1<<p),p+1,a,tail,row);
}
}
int dp(int row,int s)
{
if(f[row][s]!=-1) return f[row][s]%MOD;
int q[1<<maxn],head=0,tail=0;
int s1=~s;
s1=s1&((1<<m)-1);
for(int k=0;k<m;k++)
{
if(!isFertile[row][k]) s1=s1^(1<<k);
}
dfs(s1,0,q,tail,row);
f[row][s]=0;
if(row==n-1) return f[row][s]=tail%MOD;
for(head=0;head<tail;head++)
{
f[row][s]=(f[row][s]+dp(row+1,q[head]))%MOD;
}
return f[row][s];
}
int main()
{
cin>>n>>m;
for(int i=0;i<n;i++)
for(int j=0;j<m;j++)
cin>>isFertile[i][j];
memset(f,-1,sizeof(f));
int q[1<<maxn],head=0,tail=0;
for(int s=0;s<(1<<m);s++)
{//枚举第一行的所有合法状态
int k;
for(k=0;k<m;k++)
{
if(s&(1<<k)&&(isFertile[0][k]==0||(s&(1<<(k+1))))) break;
}
if(k>=m) {q[tail++]=s;}
}
if(n==1) {cout<<tail<<endl;return 0;}
int sum=0;
for(head=0;head<tail;head++)
sum=(sum+dp(1,q[head]))%MOD;
cout<<sum<<endl;
return 0;
}
分享到:
相关推荐
【标题】"Poj3254.rar_poj3254" 提供的是一个针对编程竞赛问题Poj3254的解决方案,这个压缩包很可能是包含源代码、注释和其他相关解释材料的集合。 【描述】"poj3254的答案, 含有比较详细的注释" 指出了解决该问题...
He wants to grow some yummy corn for the cows on a number of squares. Regrettably, some of the squares are infertile and can't be planted. Canny FJ knows that the cows dislike eating close to each ...
- 记录状态的动态规划:如`poj3254, poj2411`。 这份训练计划不仅涵盖了基础的算法和数据结构,还深入到了更复杂的概念和技巧,如图算法中的差分约束系统、最小费用最大流,以及数据结构中的线段树和RMQ。此外,还...
### POJ 3083 Children of the Candy Corn 解题报告 #### Description 题目描述了一个典型的迷宫问题:在一个玉米地迷宫中,游客需要找到从入口到出口的路径。题目给出了一个常见的策略:选择左墙或右墙并沿着它...
* 图的深度优先遍历和广度优先遍历:图的深度优先遍历和广度优先遍历是指遍历图的两种方式,如 poj1860、poj3259、poj1062、poj2253、poj1125、poj2240。 * 最短路径算法:最短路径算法是指计算图中两点之间的最短...
【标题】"POJ.rar_poj java_poj1048" 涉及的知识点主要围绕编程竞赛中的“约瑟夫环”问题,这里是一个加强版,使用Java语言进行解决。 【描述】"POJ1048,加强版的约瑟夫问题 难度中等" 提示我们,这个问题是编程...
标题中的“POJ_3131.zip_POJ 八数码_poj”指的是一个与编程竞赛网站POJ(Problem Set Algorithm)相关的项目,具体是针对3131号问题的解决方案,该问题涉及到了八数码游戏。八数码游戏,又称滑动拼图,是一个经典的...
【标题】"POJ1159-Palindrome" 是北京大学在线编程平台POJ上的一道编程题目。这道题目主要考察的是字符串处理和回文判断的知识点。 【描述】"北大POJ1159-Palindrome 解题报告+AC代码" 暗示了解决这道问题的方法和...
- (POJ3254, poj2411, poj1185):将传统动态规划技术应用于更复杂的场景。 3. **矩阵动态规划**: - (poj2057, poj1947, poj2486, poj3140):使用矩阵加速动态规划的计算过程。 ### 十二、组合数学进阶 1. **...
【标题】"POJ2002-Squares"是一个经典的计算机编程题目,源自北京大学的在线判题系统(POJ,即PKU Online Judge)。这个题目主要涉及到算法设计和实现,尤其是数学和动态规划方面的知识。 【描述】"解题报告+AC代码...
标题中的"jihe.rar_2289_POJ 3714_poj3714_poj3714 Ra_visual c" 提到了一个压缩文件,可能包含有关编程竞赛或算法解决的资源,特别是与POJ(Problem On Judge)平台上的问题3714相关的。"Ra_visual c"可能指的是...
* 较为复杂的动态规划:例如 poj1191、poj1054、poj3280、poj2029、poj2948、poj1925、poj3034。 数学 1. 组合数学: * 加法原理和乘法原理。 * 排列组合。 * 递推关系:例如 poj3252、poj1850、poj1019、poj...
- **例题**:poj1860, poj3259, poj1062, poj2253, poj1125, poj2240 - **解释**:最短路径算法包括Dijkstra算法、Bellman-Ford算法、Floyd算法以及堆优化的Dijkstra算法等。 ##### (3) 最小生成树算法 - **例题**...
标题和描述中的“poj各种分类”主要指向的是在POJ(Peking University Online Judge)平台上,根据解题策略和算法类型对题目进行的分类。POJ作为一个知名的在线编程平台,提供了大量的算法练习题,适合从初学者到...
【标题】"POJ1837-Balance"是一个在线编程竞赛题目,源自著名的编程练习平台POJ(Programming Online Judge)。这个题目旨在测试参赛者的算法设计和实现能力,特别是处理平衡问题的技巧。 【描述】"解题报告+AC代码...
poj 3414解题报告poj 3414解题报告poj 3414解题报告poj 3414解题报告
《北大POJ3083-Children of the Candy Corn解题报告及AC代码解析》 在编程竞赛的世界里,北京大学的在线判题系统POJ(Problemset of JUDGER)是一个备受程序员喜爱的平台,它提供了丰富的算法题目供参赛者挑战。...
poj 1012解题报告poj 1012解题报告poj 1012解题报告poj 1012解题报告
【标题】"POJ1201-Intervals" 是北京大学在线编程平台POJ上的一道题目,这道题目主要涉及计算机科学中的算法设计与分析,尤其是数据结构和时间复杂度优化方面的知识。 【描述】"北大POJ1201-Intervals 解题报告+AC...