算法提高课汇总

算法思路

理解题意

本题是AcWing 327. 玉米田的十字+扩展 — 影响的范围多了一格.

按照行从小到大的顺序摆放, 此时第$i$行不止受到$i - 1$行影响, 还受到$i - 2$影响. 也就是相比🌽玉米田
我们的状态需要额外一维表示多出的限制: 在🌽基础上多一维表示第$i - 1$行的状态, 枚举合法的$i - 2$行状态.

$DP$分析

状态表示 $dp(i, s_i, s_{i - 1})$

• 集合: 只摆前$i$行, 且第$i$行状态为$s_i$, 第$i - 1$行的状态是$s_{i - 1}$的所有摆法.

• 属性: Max摆放数目

状态计算

按$i - 2$行的状态对集合进行划分.

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

• 某行合法: 炮兵不能相邻或者只隔一格<-->$s$的二进制所有的1相隔的0的数目需要大于$1$.

• 三行状态在列上不重合<-->$s_i\&s_{i - 1}=0$且$s_i\&s_{i - 2}=0$且$s_{i - 1}\&s_{i - 2}=0$

• 对于第$i$行和第$i - 1$行炮兵只能在平原上. 类似$s$, $g$是某行山地的二进制表示,
  则$s_i\&g_i=0$且$s_{i - 1}\&g_{i - 1}=0$. 我们不需要考虑$i - 2$行是否在这里合法, 因为我们
  保证不计算不合法的状态, 其数值为0.

接着考虑$dp(i, s_i, s_{i - 1})$的计算: 假设$s_{i - 2}$是合法的$i - 2$行状态. 先去掉第$i$行状态,
则剩余状态对应集合为:

• 只摆前$i - 1$行, 且第$i - 1$行状态为$s_{i - 1}$, 第$i - 2$行的状态是$s_{i - 2}$的所有摆法.

对应的最大摆放数为$dp(i - 1, s_{i - 1}, s_{i - 2})$.

所以$dp(i, s_i, s_{i - 1}) = max\lbrace dp(i - 1, s_{i - 1}, s_{i - 2}) + cnt(s_i)\rbrace$. 其中$cnt(s_i)$表示第$i$行摆放炮兵数目.

代码实现

时间复杂度

$T(n) =\;$状态数目$\;\times \;$状态计算 = $n\cdot 2^m\cdot 2^m\times 2^m$. 类似的, 由于合法条件的限制, 在预处理合法状态后, 需要枚举的状态非常少.

空间优化

使用滚动窗口的空间优化方法: 因为第$i$行状态仅依赖于$i - 1$行, 所以可以交替使用0与1表示当前行
和上一行的状态. 实现时因为第一维奇偶交替, 所以$i\&1$即可实现.

计算出口

这里多枚举了一行状态, 输出时我们需要枚举到$n + 2$行, 以此保证$n + 1$行的状态为$0$.

具体代码

#include <vector>
#include <iostream>

using namespace std;

const int N = 110, M = 12, S = 1 << 10;

int n, m;
int g[N], cnt[S];
int dp[2][S][S];
vector<int> state;

int count(int s)
{
    int res = 0;
    while( s )
    {
        res += s & 1;
        s >>= 1;
    }
    return res;
}

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

int main()
{
    cin >> n >> m;
    for( int i = 1; i <= n; i ++ )
    {
        char c;
        for( int j = 0; j < m; j ++ )
        {
            cin >> c;
            if( c == 'H' )  g[i] += 1 << j;
        }
    }

    for( int s = 0; s < 1 << m; s ++ )
    {
        if( check(s) )
        {
            cnt[s] = count(s);
            state.push_back(s);
        }
    }

    for( int i = 1; i <= n + 2; i ++ )
    {
        for( int s : state )  //第i行状态
        {
            if( s & g[i] )  continue;
            for( int s1 : state )  // 第i - 1行状态
            {
                if( (s1 & s) | (s1 & g[i - 1]) )    continue;
                for( int s2 : state )  // 第i - 2行状态
                {
                    if( (s & s2) | (s1 & s2) )  continue;

                    dp[i & 1][s][s1] = max( dp[i & 1][s][s1], 
                        dp[i - 1 & 1][s1][s2] + cnt[s] );
                }
            }
        }
    }
    cout << dp[n + 2 & 1][0][0] << endl;

    return 0;
}