一个n*n的棋盘，要在上面放国王，每个国王占领周围3*3的土地，求放置K个国王的方案数量。

一开始感觉结论题就打了个表，打一个8的表只要一两分钟⬇️，虽然说n<=9，但是9的估计要很久...说不定考试那几个小时都打不完。

 

 

 

说说正解吧。

考虑壮压dp，如果按照一个个位置dp需要记录轮廓线以及左上角那个位置的情况，但是显然我们不需要那么复杂。

情况数2^9=512   预先处理好  每种情况是否合法  需要多少国王  两种情况之间是否可以转移  ，就可以啦。

f[i][j][k]表示前i行用了j个国王，第i行状态是k的个数。复杂度n*K*2^(2*n)

#include
     
      #include
      
       #define ll long longusing namespace std;inline int read(){    int x=0,f=1;char ch=getchar();    while(ch<'0'||ch>'9'){
   if(ch=='-') f=-1;ch=getchar();}    while(ch>='0'&&ch<='9'){x=x*10+ch-'0'; ch=getchar();}    return x*f;}bool b[515][515];int n,K;ll f[10][105][515];int use[515];int main(){    n=read();K=read();int to=(1<
       
        >=1;        }        if(use[i]!=-1) use[i]=tot;    }    for(int i=0;i
        
         >1)))||(j&(k<<1))||(j&k)))                    {b[i][j]=0;break;}            }    f[0][0][0]=1;    for(int i=1;i<=n;i++)        for(int j=0;j<=K;j++)            for(int k=0;k