題目鏈接：https://vjudge.net/contest/224636#problem/G

轉載于：https://blog.csdn.net/harrypoirot/article/details/23163485

?

題目大意：

農夫有一塊地，被劃分為m行n列大小相等的格子，其中一些格子是可以放牧的（用1標記），農夫可以在這些格子里放牛，其他格子則不能放牛（用0標記），并且要求不可以使相鄰格子都有牛。現在輸入數據給出這塊地的大小及可否放牧的情況，求該農夫有多少種放牧方案可以選擇（注意：任何格子都不放也是一種選擇，不要忘記考慮！

?

解題分析就看上面那篇博客，我也是照著上面學的。

#include <cstdio> #include <cstring> using namespace std;#define mod 100000000 int M, N, top = 0; //top表示每行最多的狀態數int state[600]; //state存放每行所有的可行狀態（即沒有相鄰的狀態)int dp[20][600]; //dp[i][j]:對于前i行數據，第i行有前j種可能狀態時的解 int cur[20]; //cur[i]表示的是第i行整行的情況 inline bool ok(int x) { //判斷狀態x是否可行if (x&x << 1) return false;//若存在相鄰兩個格子都為1，則該狀態不可行return true; }void init() { //遍歷所有可能的狀態top = 0;int total = 1 << N; //遍歷狀態的上界for (int i = 0; i < total; ++i) { //總共有total種狀態需要討論if (ok(i))state[++top] = i; //state[]為一行中所有可行的狀態 } }//原理就是，如果你在不能夠放1的位置放了1，那么這個方案肯定不可行 inline bool fit(int x, int k) { //判斷狀態x 與第k行的實際狀態的逆是否有‘重合’ //判斷理論上每一行能符合的情況是否與某一特定的行符合，因為每一行規定了能放1的位置if (x&cur[k])return false; //若有重合，（即x不符合要求)return true; //若沒有，則可行 }int main() {while (scanf("%d%d", &M, &N) != EOF) {init();memset(dp, 0, sizeof(dp));for (int i = 1; i <= M; ++i) {cur[i] = 0;int num;for (int j = 1; j <= N; ++j) { //輸入時就要按位來存儲，cur[i]表示的是第i行整行的情況，每次改變該數字的二進制表示的一位scanf("%d", &num); //表示第i行第j列的情況（0或1）if (num == 0) //若該格為0 cur[i] += (1 << (N - j)); //則將該位置為1（注意要以相反方式存儲，即1表示不可放牧} //cur[]數組，利用狀態壓縮，用一維數組，表示了二維的數據 }for (int i = 1; i <= top; i++) {if (fit(state[i], 1)) { //判斷所有可能狀態與第一行的實際狀態的逆是否有重合dp[1][i] = 1; //若第1行的狀態與第i種可行狀態吻合，則dp[1][i]記為1 }} //先算出第一行的情況，初始化dp[1][]的所有情況，方便下面dp的遞推，//前面的都是準備工作，都是為了下面的這個狀態轉移方程做準備for (int i = 2; i <= M; ++i) { //i索引第2行到第M行for (int k = 1; k <= top; ++k) { //該循環針對所有可能的狀態，找出一組與第i行相符的state[k]if (!fit(state[k], i))continue; //判斷是否符合第i行實際情況for (int j = 1; j <= top; ++j) { //找到state[k]后，再找一組與第i-1行符合，且與第i行（state[])不沖突的狀態state[j]if (!fit(state[j], i - 1))continue; //判斷是否符合第i-1行實際情況 //找出上一行的所有可行狀態if (state[k] & state[j])continue; //判斷是否與第i行沖突 //判斷第i行的狀態是否與上一行沖突dp[i][k] = (dp[i][k] + dp[i - 1][j]) % mod; //若以上皆可通過，則將'j'累加到‘k'上 } //這里就相當于dp[i][k]+=dp[i-1][j],只不過因為要取模運算，所以寫成這樣} //狀態轉移方程的根據為，dp[i][k]表示第i行采用方案k時，前i總共有多少種可行的情況 }int ans = 0;for (int i = 1; i <= top; ++i) { //累加最后一行所有可能狀態的值，即得最終結果！！！ans = (ans + dp[M][i]) % mod; }printf("%d\n", ans);} }

?

?

2018-07-26

?

轉載于:https://www.cnblogs.com/00isok/p/9370993.html

總結

以上是生活随笔為你收集整理的Poj - 3254 Corn Fields (状压DP)（入门）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。