POJ 3254 Corn Fields 题解 《挑战程序设计竞赛》

POJ 3254 Corn Fields

种玉米：农夫约翰有n*m块地，其中一些地荒掉了。玉米是一种傲娇的植物，种在相邻的地里会导致不孕不育。求所有种法数对100000000求余。

3.4熟练掌握动态规划

状态压缩DP

今天换了CLion，拿这题试试刀~

定义dp[i][S] := 第i行的状态为S时的方法总数，每一行的种法取决于前一行的种法以及这一行的坏块。熟练掌握位运算就能轻松枚举。

#include <iostream>
#include <cstdio>

using namespace std;

int dp[12][1 << 12];    // dp[i][S] := 第i行的状态为S时的方法总数
int bad[12];            // 荒地的mask
int MOD = 100000000;
int m, n;

//************************************
// Method:    dfs
// FullName:  dfs
// Access:    public 
// Returns:   void
// Qualifier: 遍历一行
// Parameter: int row y坐标
// Parameter: int line x坐标
// Parameter: int S 当前集合
// Parameter: int except_S 排除集合(也就是上一行地的状态加上这一行荒地的状态)
// Parameter: int pre_dp 上一行对应的个数
//************************************
void dfs(int row, int line, int S, int except_S, int pre_dp)
{
   if (line == n)                              // 这一行种完了，统计结果
   {
      dp[row][S] = (dp[row][S] + pre_dp) % MOD;
      return;
   }
   dfs(row, line + 1, S, except_S, pre_dp);    // 这一行还没有种完，继续尝试往下种
   if (!(except_S & (1 << line)))  // 无重叠
   {
        // 这里的S | 1 << line将line加入集合，except_S | (1 << (line + 1))表示排除相邻的一个
      dfs(row, line + 1, S | 1 << line, except_S | (1 << (line + 1)), pre_dp);
   }
}

///////////////////////////SubMain//////////////////////////////////
int main(int argc, char *argv[])
{
#ifndef ONLINE_JUDGE
   freopen("in.txt", "r", stdin);
#endif
   cin >> m >> n;
   for (int i = 0; i < m; ++i)
   {
      for (int j = 0; j < n; ++j)
      {
         int t;
         cin >> t;
         bad[i] |= (!t) << j;
      }
   }

   dfs(0, 0, 0, bad[0], 1);
   for (int i = 1; i < m; ++i)
   {
      for (int j = 0; j < (1 << n); ++j)
      {
         dfs(i, 0, 0, bad[i] | j, dp[i - 1][j]); // bad[i] | j表示上一行的状态j和这一行的荒地合并加入到排除集合中
      }
   }
   int ans = 0;
   for (int i = 0; i < (1 << n); ++i)
   {
      ans = (ans + dp[m - 1][i]) % MOD;
   }
   cout << ans << endl;
#ifndef ONLINE_JUDGE
   fclose(stdin);
#endif
   return 0;
}
///////////////////////////End Sub//////////////////////////////////

 知识共享署名-非商业性使用-相同方式共享：码农场 » POJ 3254 Corn Fields 题解 《挑战程序设计竞赛》