POJ 3254 Corn Fields(状态压缩DP)

Description

给出N x M 的01矩阵，1表示该处可种植作物，0表示不可以。另外相邻两块地不能同时种植作物，问有几种种植作物的方案(并没有规定种几棵作物)

状态压缩

for(int i = 0; i < (1 << n); ++i)

用一个数来表示一组数，以降低表示状态所需的维数的解题手段，就叫做状态压缩

solution

以dp[i][state(j)]来表示对于前i行，第i行采用第j种状态时可以得到的可行方案总数

dp[i][state(j)]=dp[i - 1][state(k1)]+dp[i - 1][state(k2)]+……+dp[i - 1][state(kn)]

kn即为上一行可行状态的编号，上一行共有n种可行状态

(把不可行状态排除掉：同行相邻、同列相邻、理想与现实冲突)

最终ans=dp[m][state(k1)]+dp[m][state(k2)]+……+dp[m][state(kn)];

原文出处：https://blog.csdn.net/harrypoirot/article/details/23163485

Code

#include <cstdio>
#include <iostream>
using namespace std;
const int MOD = 100000000;

bool e[15][15], in[1 << 14];
int dp[15][1 << 14], n, m;
///dp[i][state(j)]来表示对于前i行，第i行采用第j种状态时可以得到的可行方案总数



///检测理想方案是否与现实冲突
bool solve(int S, int l)///S -> set   l -> line
{
    for (int i = 1; i <= m; i++)
        if (!e[l][i] && (S & (1 << (m - i)))) /// 如果本来不能种,该状态种了
            return false;
    return true;
}

int main()
{
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            cin >> e[i][j];

    ///初始化(1):找出所有理想方案里的可行方案
    for (int S = 0; S < (1 << m); S++)
        if((S & (S << 1)) == 0)///同一行里无相邻的1
            in[S] = true;

    ///初始化(2):找出所有理想方案中不与现实冲突的方案
    for (int S = 0; S < (1 << m); S++)
        if (in[S] && solve(S, 1))
            dp[1][S] = 1;

    /// (j & S)筛选掉同列的状态 ;
    for (int i = 2; i <= n; i++)
        for (int j = 0; j < (1 << m); j++)
            for (int S = 0; S < (1 << m); S++)
                if (in[j] && solve(j, i) && !(j & S))
                    dp[i][j] = (dp[i][j] + dp[i - 1][S]) % MOD;

    int ans = 0;
    for (int S = 0; S < (1 << m); S++)
        ans = (ans + dp[n][S]) % MOD;
    cout << ans << '\n';
    return 0;
}

动态规划

1. 状态设定
2. 状态转移
3. 初始化(边界处理)

状态转移方程一定要仔细推敲，不可一带而过，要思考为什么这么做，掌握一个套路，遇见这类问题能快速的识别出问题的本质，找出状态转移方程和DP的边界条件。