算法提高课汇总

算法思路

理解题意

思路大致与AcWing 1064. 小国王类似, 与其异同点:

1. 限制由井田口变为十字+.
2. 没有数量限制.
3. 某些区域不能放置.

$DP$分析

状态表示$dp(i, s)$

• 集合: 只从前$i$行摆放, 且第$i$行摆放状态为$s$(二进制表示)的所有摆放方案.

• 属性: Count方案数

状态计算

类似的, 我们按行从小到大的顺序摆放, 这样做的好处是当摆放第$i$行时, 其仅受$i - 1$行摆放的影响. 所以
可以按照第$i - 1$行的摆放状态作为集合划分依据.

首先考虑哪些状态是合法的?

• 某行合法: 没有相邻的玉米🌽 <--> 二进制表示没有相邻1.

• 对于第$i$行状态$s_i$, 合法的$i - 1$状态$s_{i - 1}$满足: 本身是合法的行状态; 玉米🌽不在列上重合
  <--> $s_i\;\&\;s_{i - 1} = 0$.

状态$dp(i,s_i)$的计算: $dp(i, s_i) = \sum dp(i - 1, s_{i - 1})$. 相关分析见AcWing 1064. 小国王.

代码实现

• 为方便计算, 对于某行不能种植的位置采用状态$s$的相同思路: 二进制位为1表示对应的列无法种植.

具体代码:

#include <vector>
#include <iostream>

using namespace std;

const int N = 14, M = 1 << 12, mod = 1e8;

int n, m;
int g[N]; //无法种植的位置 二进制表示
int dp[N][M];
vector<int> state; //单行合法状态
vector<int> head[M]; //head[si]: 对于i行状态si, 所有合法的第i - 1行状态

bool check(int s)
{
    if( (s & (s << 1)) || (s & (s >> 1)) )
        return false;
    return true;
}

int main()
{
    cin >> n >> m;
    for( int i = 1; i <= n; i ++ )
        for( int j = 0; j < m; j ++ )
        {
            int t;
            cin >> t;
            g[i] += !t << j; //用1表示无法终止 与题目规定相反
        }

    for( int s = 0; s < 1<<m; s ++ )
        if( check(s) )
            state.push_back(s);

    for( int s : state )
        for( int s1 : state )
            if( (s & s1) == 0 )
                head[s].push_back(s1);

    dp[0][0] = 1; //初始唯一合法状态 方案数为1
    for( int i = 1; i <= n + 1; i ++ )
        for( int s : state )
        {
            if( s & g[i] )  continue; //无法种植

            for( int s1 : head[s] )
                dp[i][s] = ( dp[i][s] + dp[i - 1][s1] ) % mod;
        }
    cout << dp[n + 1][0] << endl;

    return 0;
}