原题
先思考怎么表示状态，用f[i][j]表示第i行放j个显然不行，那么需要一个可以表示出状态的变量，由于m很小，可以用二进制表示每个位置是否放置，因此f[i][j][z]表示第i行放置状态j时共放置z个国王的方案数，本行只收上一行的状态。
我用的是状压dfs，和状压dp想法一样，而且比较好实现，另外复杂度相同。
状压dfs（((2^n)^2)*k*n）最坏情况1e9，可以ac。
x表示行，y是列（从0），zhuang是你所求的上一行的状态，net是本行的状态（即本行的zhuang），now表示现有的国王总数，start存初值，l保证国王不相邻（其实可以直接跳两步，就不需要l了）
#include<iostream> #include<iomanip> #include<cstdio> #include<cstring> #include<algorithm> using namespace std; int n,m,k,cnt,f[11][1125][101]; int dfs(int x,int y,int zhuang,int net,int now,int start,int l) { if(y==n) { f[x+1][net][now]+=start; return 0; } dfs(x,y+1,zhuang,net,now,start,l); if(now<k&&(((1<<y)&zhuang)==0)&&y-l>1) { net=net|(1<<y); if(y>0) net=net|(1<<y-1); if(y<n-1) net=net|(1<<y+1); dfs(x,y+1,zhuang,net,now+1,start,y); } } int main() { cin>>n>>k; memset(f,0,sizeof(f)); f[1][0][0]=1; for(int i=1;i<=n;++i) for(int j=0;j<(1<<n);++j) for(int z=0;z<=k;++z) if(f[i][j][z]) dfs(i,0,j,0,z,f[i][j][z],-2); int ans=0; for(int i=0;i<(1<<n);++i) ans+=f[n+1][i][k]; cout<<ans; return 0; }
注意：洛谷的数据更改，需要将int改为长整型
