算法提高课汇总

算法思路

理解题意

1. 限制
   • 摆放国王个数
   • 每个国王不能在相邻8个格子内
2. 目的
   • Count摆放方案数

我们可以按照行从小到达的顺序摆放国王, 这带来解题的简便: 第$i$行如何摆放只受限于$i - 1$行
的状态. 以每一行摆放国王的状态作为集合划分依据, 利用$DP$求解. 这里的思路类似于
AcWing 291. 蒙德里安的梦想, 后面也会提到两者思路的相同点.

$DP$分析

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

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

• 属性: Count方案数

状态计算

第$i$行摆放方案只受限于第$i - 1$行, 所以将$i - 1$行的状态作为集合划分依据. 首先考虑哪些方案是
合法方案:

1. 某一行合法: 没有相邻的国王. 首先第$i$行和第$i - 1$行的状态必须合法.

2. 对于$i$的状态$s_i$, $i - 1$的状态$s_{i - 1}$合法:

   • 列不重合, $s_i\;\&\;s_{i - 1} = 0$
   • 将两列状态放在同一列后没有相邻国王: $s_i\mid s_{i - 1}$没有相邻的1.

对于$s_i$的合法方案$s_{i - 1}$, 方案计数的思路类似于AcWing 11. 背包问题求方案数. 我们可以先不考虑第$i$行, 则此时的状态为:

• 只摆放前$i - 1$行, 摆放国王个数为$j - cnt(s_i)\;$($cnt(s_i):s_i状态对应国王个数$), 且$i - 1$行的状态
  为$s_{i - 1}$. 根据状态定义, 其方案数为$dp(i - 1, j - cnt(s_i), s_{i - 1})$.

所以$dp(i, j, s_i) = \sum dp(i - 1, j - cnt(s_i), s_{i - 1})$.

直观理解: 对于状态$dp(i - 1, j - cnt(s_i), s_{i - 1})$的所有方案, 我们在第$i$行放入国王$s_i$后仍然
合法, 且方案数不变.

代码实现

时间复杂度

$DP$时间复杂度—状态个数$\times$状态计算 $=\;N\cdot N^2\cdot 2^N\times 2^N$. 这样看来算法超时. 但实现时我们可以预处理某一行的合法状态, 以及对于状态$s_i$其合法的上一行状态$s_{i - 1}$. 这样$2^N\times 2^N$将降至$1e3$级别.

具体代码

#include <vector>
#include <iostream>

using namespace std;

typedef long long ll;

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

int n, m;
int cnt[S]; //cnt[s]: 状态s对应国王个数, 即二进制1的个数
ll dp[N][M][S]; 
vector<int> state; //行合法状态
vector<int> head[S]; //head[s]: 对于第i行状态s, 其i-1行的所有合法状态

bool check(int s)
{//单行状态s是否合法: 二进制没有相邻数字1
    if( (s & (s << 1)) || (s & (s >> 1)) )
        return false;
    return true;
}

int count(int s)
{//s二进制1的个数
    int res = 0;
    while( s )
    {
        res += s & 1;
        s >>= 1;
    }
    return res;
}

int main()
{
    cin >> n >> m;

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

    for( int s : state )
    {
        for( int s1 : state )
        {
            if( (s & s1) == 0 && check(s | s1) ) //注意s&s1需要加括号 &的优先级低于==
                head[s].push_back(s1);
        }
    }

    dp[0][0][0] = 1; //i = 0时的唯一合法状态, 状态对应方案数为1
    for( int i = 1; i <= n + 1; i ++ )
    {
        for( int j = 0; j <= m; j ++ )
        {
            for( int s : state )
            {
                if( j < cnt[s] )    continue; //第i行状态s对应国王数 > 所有国王数,不合法

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

    return 0;
}

小结

本题与AcWing 291. 蒙德里安的梦想有类似的地方:

• 本题国王按行的顺序摆放, Acwing 291按列的顺序摆放. 好处是简化当前状态所受限制的状态数目.

• 计数: 当前状态方案数等于能到达这个状态的所有合法状态的方案数.

• 出口: 都机智的采取多算一行/一列的方式得到最终解.