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。此外,还...
2. **记忆化搜索**:结合动态规划和递归搜索(POJ3254, poj2411, poj1185)。 3. **多维动态规划**:处理多个维度的状态(poj2057, poj1947, poj2486, poj3140)。 ### 十五、进阶数学 1. **数列和级数**:数列...
### POJ 3083 Children of the Candy Corn 解题报告 #### Description 题目描述了一个典型的迷宫问题:在一个玉米地迷宫中,游客需要找到从入口到出口的路径。题目给出了一个常见的策略:选择左墙或右墙并沿着它...
【标题】"POJ.rar_poj java_poj1048" 涉及的知识点主要围绕编程竞赛中的“约瑟夫环”问题,这里是一个加强版,使用Java语言进行解决。 【描述】"POJ1048,加强版的约瑟夫问题 难度中等" 提示我们,这个问题是编程...
* 图的深度优先遍历和广度优先遍历:图的深度优先遍历和广度优先遍历是指遍历图的两种方式,如 poj1860、poj3259、poj1062、poj2253、poj1125、poj2240。 * 最短路径算法:最短路径算法是指计算图中两点之间的最短...
【标题】"POJ1159-Palindrome" 是北京大学在线编程平台POJ上的一道编程题目。这道题目主要考察的是字符串处理和回文判断的知识点。 【描述】"北大POJ1159-Palindrome 解题报告+AC代码" 暗示了解决这道问题的方法和...
- (POJ3254, poj2411, poj1185):将传统动态规划技术应用于更复杂的场景。 3. **矩阵动态规划**: - (poj2057, poj1947, poj2486, poj3140):使用矩阵加速动态规划的计算过程。 ### 十二、组合数学进阶 1. **...
标题“POJ3253-POJ3253-Fence Repair【STL优先队列】”指的是一个在线编程竞赛题目,源自北京大学的在线判题系统POJ(Problem Online Judge)。该题目要求参赛者使用C++编程语言解决特定的问题,并且在解决方案中...
【标题】"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"可能指的是...
这些题目是针对ACM竞赛(ACM International Collegiate Programming Contest,简称ICPC)中的编程训练,POJ(Problem Set for Online Judges)是一个在线的编程竞赛平台,提供了许多算法和逻辑思维的练习题目。...
* 较为复杂的动态规划:例如 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解题报告