1. 题目

传送门= ̄ω ̄=

2. 题解

这题一看就可以状压。
可以一个格子一个格子地搜索,记录上一行的状态。
我的做法是先预处理出一行中可能的所有状态(即这一行上的国王都不会互相攻击),再在动归过程中枚举这一行的状态,与上一行比较,这样一整行一整行地搜,理论上会快一点吧。

代码:

#include <bits/stdc++.h>
using namespace std;
int n,m,st[300],stc,f[10][100][1000],ans;
void initdfs(int c,int k)
{
    if(c>n){st[stc++]=k;return;}
    initdfs(c+1,k);
    if(!(k&(1<<(c-1))))initdfs(c+1,k|(1<<c));
}
int dfs(int c,int l,int k)//当前搜到了第 c 行,放了 l 个棋子,上一行状态为 k
{
    for(int i=1;i<=n;i++)l+=((k>>i)&1);
    if(f[c][l][k]!=-1)return f[c][l][k];
    if(l==m)return f[c][l][k]=1;
    if(c>n||l>m)return f[c][l][k]=0;
    f[c][l][k]=0;
    for(int i=0;i<stc;i++)
        if(!(k&st[i])&&!((k<<1)&st[i])&&!((k>>1)&st[i]))
            f[c][l][k]+=dfs(c+1,l,st[i]);
    return f[c][l][k];
}
int main()
{
    scanf("%d%d",&n,&m),initdfs(1,0),memset(f,-1,sizeof(f));
    printf("%d\n",dfs(1,0,0));
    return 0;
}
分类: 文章

XZYQvQ

炒鸡辣鸡的制杖蒟蒻一枚QvQ

1 条评论

【题解】四个国王 动态规划 状态压缩 codevs – 1698 – K-XZY · 2017年5月17日 10:27 下午

[…] 同 http://k-xzy.cf/?p=1320。 改下代码就行了。 […]

发表回复

Avatar placeholder

您的电子邮箱地址不会被公开。 必填项已用 * 标注