POJ 3254 Corn Fields 状压DP - c++编程基础

TOP

POJ 3254 Corn Fields 状压DP

2015-07-20 18:06:00 来源: 作者: 【大中小】浏览:4次

题意：一块M*N的田地，每小块地大小是1*1，可以种植物的标记为1，不可以种植物的标记为0，并且相邻的两块地不可以同时种植物。问题是有多少种不同的种植方案（所有地都不种也是一种种植方案）

思路：这是第一道状压DP题，从第一行更新到最后一行，每一行用一个N位的二进制数来表示该行的状态1表示该位置种了植物，0表示该位置没种植物。因为每块地只对相邻的土地能否种植有所影响，所以每一行的状态可以用前一行的状态递推得到。

资料：http://www.doc88.com/p-771373748581.html

代码：

#include
  
   
#include
   
     #include
     #include
     
       #include
      
        #include
       
         #include
        
          #include
         
           #define MOD 100000000 using namespace std; int dp[15][40000]; bool judge(int x) { if((x&(x<<1))==0) return 1; return 0; }//函数用来判断i状态是否有相邻的土地种植了植物，如果没有，返回1 int main() { int row,col,x; int field[15]; memset(field,0,sizeof(field)); memset(dp,0,sizeof(dp)); scanf(%d%d,&row,&col); for(int i=0; i
          
           ?


【大中小】【打印】【繁体】【投稿】【收藏】【推荐】【举报】【评论】【关闭】【返回顶部】
分享到:
上一篇：POJ 1837 Balance DP	下一篇：HDU 1231 最大连续子序列 (动规)

帐　　号:

密码: (新用户注册)

验证码:

表　　情:

内　　容: