题目链接:Luogu P1896/BZOJ 1087/LibreOJ 2153/SCOI2005 D2T2。
一道 状压 \(\texttt{dp}\) 的入门题目,或者一道简单的打表题。
未完待续(时空限制)。
题目
题目描述
在 $N\times N$ 的棋盘里面放 $K$ 个国王,使他们互不攻击,共有多少种摆放方案。国王能攻击到它上下左右,以及左上左下右上右下八个方向上附近的各一个格子,共 $8$ 个格子。
数据范围
变量 | 数据范围 |
\(N\) | \(1\leq N\leq 9\) |
\(K\) | \(0\leq K\leq N^2\) |
时空限制
题目编号 | 时间限制 | 空间限制 |
$$\text{Luogu}:1\text{s}/125\text{MiB}$$ | ||
$$\text{BZOJ}:10\text{s}/162\text{MiB}$$ | ||
$$\text{LibreOJ}:1\text{s}/256\text{MiB}$$ |
题解
解法 A(状压 \(\texttt{dp}\))
思路
考虑到数据范围 $1\leq n\leq 9$,不妨用二进制数 $x$ 来表示某一行的放置状态,用 $f_{i,j,S}$ 表示当第 $i$ 行状态为 $j$ 时,已经放置了 $S$ 个国王的总方案数。
那么有:
\[f_{i,j,S}=\sum f_{i-1,k,T}\]
然后可以得出:
\[\text{ans}=\sum f_{n,i,K}\]
代码
状压 \(\texttt{dp}\) 的代码略。
解法 B(打表)
思路
考虑 $1\leq n\leq 9,0\leq k\leq n^2$,计算得出,输入总共有 $\sum^9_{i=1}i\times(i^2+1)=2070$ 种可能,比较少,所以选择打表,用解法 A 打表,实现快速输出答案。
代码
渐进时间复杂度为 $\Theta(1)$ 的程序。
#include<bits/stdc++.h> using namespace std; typedef long long ll; //本题答案超过了 int 范围 const ll ans[10][82]={ {}, //空开 ans[0][] {1,1}, {1,4,0,0,0}, {1,9,16,8,1,0,0,0,0,0}, {1,16,78,140,79,0,0,0,0,0,0,0,0,0,0,0,0}, {1,25,228,964,1987,1974,978,242,27,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0}, {1,36,520,3920,16834,42368,62266,51504,21792,3600,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0}, {1,49,1020,11860,85275,397014,1220298,2484382,3324193,2882737,1601292,569818,129657,18389,1520,64,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0}, {1,64,1806,29708,317471,2326320,12033330,44601420,119138166,229095676,314949564,305560392,204883338,91802548,25952226,4142000,281571,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0}, {1,81,2968,65240,962089,10087628,77784658,450193818,1979541332,6655170642,17143061738,33787564116,50734210126,57647295377,49138545860,31122500764,14518795348,4959383037,1237072414,224463798,29275410,2673322,163088,6150,125,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0}, }; //打成的表 int n,K; int main(void){ scanf("%d%d",&n,&K); //读入 printf("%lld\n",ans[n][K]); //输出 return 0; }
近期评论